C++ 折半查找

静态查找表中折半查找算法的实现

注意：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

#include<iostream>
using namespace std;
#define ENDFLAG 10000
typedef int KeyType;
typedef char * InfoType;
typedef struct
{
 KeyType key;
 InfoType otherinfo;
}ElemType;
typedef struct
{
 ElemType *R;
 int length;
}SSTable;
void CreateSTable(SSTable &ST,int n)
{
 int i;
 ST.R=new ElemType[n+1];
 cout<<"请输入"<<n<<"个测试数据：";
 for(i=1;i<=n;i++)
  cin>>ST.R[i].key; 
 ST.length=n;
}
int Search_Bin1(SSTable ST,KeyType key)
{
 int low,high,mid;
 low=1;
 high=ST.length;
 while(low<=high)
 {
  mid=(low+high)/2;
  if(key==ST.R[mid].key) return mid;
  else if(key<ST.R[mid].key) high=mid-1;
  else low=mid+1;
 }
 return 0;
}
int Search_Bin2(SSTable ST,int low,int high,KeyType key)
{
 int mid;
 if(low>high) return 0;
 mid=(low+high)/2;
 if(key==ST.R[mid].key) return mid;
 else if(key<ST.R[mid].key) return Search_Bin2(ST,low,mid-1,key);
 else return Search_Bin2(ST,mid+1,high,key);
}

void main()
{
 int n;
 KeyType key;
 SSTable ST;
 cout<<"请输入静态查找表长：";
 cin>>n;
 CreateSTable(ST,n);
 cout<<"请输入待查记录的关键字：";
 cin>>key;
 cout<<"Search_Bin1算法计算的位置为："<<Search_Bin1(ST,key)<<endl;
 cout<<"Search_Bin2算法计算的位置为："<<Search_Bin2(ST,1,ST.length,key)<<endl;
}