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

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

#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;

}