/*对半查找递归算法，算法作为有序表（ordered list）模板类的成员函数*/
#include<iostream>
using namespace std;
template<class T,int size>
class Orderedlist
{
private:
int maxsize;
int last;
T slist[size];
public:
Orderedlist()
{
last=-1;
maxsize=size;
}
int Binarysearch(T&x,int low, int high);
bool Insert(T &elem,int i);
void print();
};
template<class T,int size>
int Orderedlist<T,size>::Binarysearch(T & x,int low, int high)
{
int mid=-1;
if(low<=high)
{
mid=(low+high)/2;
if(slist[mid]<x)
{
mid=Binarysearch(x,mid+1,high);
}
else if(x<slist[mid])
{
mid=Binarysearch(x,low,mid-1);
}
}
return mid;
}
template<class T,int size>
bool Orderedlist<T,size>::Insert(T& elem,int i)
{
int j;
if(i<0 || i>last+1 || last==maxsize-1)
{
cout<<"添加数据失败"<<endl;
return false;
}
else
{
last++;
for(j=last;j>i;j--)
slist[j]=slist[j-1];
}
slist[i]=elem;
return true;
}
template<class T,int size>
void Orderedlist<T,size>::print()
{
int i;
for(i=0;i<=last;i++)
{
slist[i].show();
if(i%5==4)
{
cout<<endl;
}
}
}
class Element{
private:
int key;
public:
bool operator<(Element ele)
{
return key<ele.key;
}
void putkey(int k)
{
key=k;
}
void show()
{
cout<<key<<'/t';
}
};
int main()
{
const int h=19;
int i,k=37;
Orderedlist<Element,100>ord;
int a[h]={67,61,59,53,47,43,41,37,31,29,23,19,17,13,11,7,5,3,2};//降序
Element n[h],elem;
for(i=0;i<h;i++)
n[i].putkey(a[i]);
for(i=0;i<h;i++)//始终从0号元素插入，建立升序顺序表
ord.Insert(n[i],0);
elem.putkey(k);
ord.print();
cout<<endl;
i=ord.Binarysearch(elem,0,h-1);
if(i != -1)
{
cout<<"整数"<<k<<"在表中的下标是"<<i<<endl;
}
else
{
cout<<"您要查找的数据不在表中"<<endl;
}
return 0;
}
/*template<class T,int size>//二分法的迭代算法
int Orderedlist<T,size>::Binarysearch(T& x)const
{
int high=last,low=0,mid;
if(last==-1)
return -1;
while(low<=high)
{
mid=(low+high)/2;
if(x<slist[mid])
{
high=mid-1;
}
else if(slist[mid]<x)
{
low=mid+1;
}
else
return mid;
}
if(slist[mid]!=x)
mid=-1;
return mid;
}*/