#include <iostream>
using namespace std;
typedef int KeyType;
struct ElemType {KeyType key;};
struct SList {ElemType *r;int length;};
int Search_Bin(SList &L,KeyType k);//有序表的折半查找算法
bool ListCreate(SList &L,int n,KeyType a[]);
int ReSea_Bin(SList L,KeyType k,int a,int b);
int ReSea_Bin(SList L,KeyType k);//递归
int main()
{
SList L; int length=11;
//KeyType k=1;
//KeyType k=67;
KeyType k=67;
KeyType a[11]={01,03,11,15,17,26,33,45,53,67,72};
ListCreate(L,length,a);
cout<<"原顺序表为"<<endl;
for(int j=0;j<length;j++){cout << L.r[j].key<<" ";}
int b=ReSea_Bin(L,k);
if(b>=0)
cout<<"\n在顺序表中"<<k<<"的位置是："<<b<<endl;
else
cout<<"\n顺序表中未找到"<<k<<endl;
return 0;
}
int ReSea_Bin(SList L,KeyType k,int a,int b)
{
int m;
if(b<a)return -1;
m=(a+b)/2;
if(L.r[m].key==k)return m;
if(L.r[m].key>k) return ReSea_Bin(L,k,a,m-1);
else return ReSea_Bin(L,k,m+1,b);
}
int ReSea_Bin(SList L,KeyType k)
{
int a=0,b=L.length-1;
return ReSea_Bin(L,k,a,b);
}
int Search_Bin(SList &L,KeyType k)
{
int a,m,b;
a=0;b=L.length;
while(a<=b)
{
m=(a+b)/2;
if(L.r[m].key==k)return m;
else if(L.r[m].key<k) a=m+1;
else b=m-1;
}
return -1;
}
bool ListCreate(SList &L,int n,KeyType a[])
{
int i;
L.r=new ElemType[n];
if(!L.r) return false;
L.length=n;
for(i=0;i<n;i++)
{
L.r[i].key=a[i];
}
return true;
}