数据结构与算法----3.1 实现递归形式的折半查找算法

[c++]代码库

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