資料結構 折半查找

#include<iostream>
using namespace std;
#include<stdlib.h>//使用資料庫srand和rand 
#include<time.h>//使用庫資料time
const int Max=10;//假定帶查找集合有10個元素

void Creat(int a[]);
int BinSearch(int r[],int n,int k,int &count);//有序表r[],有序表的資料個數為n，設帶查找元素為k，查詢次數為count
int main()
{
	int a[Max+1]={0};//假設
	int location=0,count=0,k;
	Creat(a);
	for(int i=1;i<=Max;i++)
	cout<<a[i]<<" ";
	cout<<endl;
	k=a[1+rand()%Max];//随機生成帶查找元素的下标 
	location=BinSearch(a,Max,k,count);
	cout<<"元素"<<k<<"在序列中序号是"<<location;
	 cout<<",共比較"<<count<<"次"<<endl;
	 return 0; 
	
} 
void Creat(int a[])//函數定義，随機生成待查找集合 
{
	srand(time(NULL));//初始化随機種子為目前系統随機時間 
	
	a[0]=0;
	for(int i=1;i<=Max;i++)
	a[i]=a[i-1]+rand()%Max;//生成一個遞增序列
	 
}
int BinSearch(int r[],int n,int k,int &count)//從數組下标1開始存放待查集合
{
int low=1;
int high=n;//設定查找區間 
int mid;
while(low<=high)//當期間存在時
{
mid=(low+high)/2;
count++;
if(k<r[mid])
high=mid-1;
else if(k>r[mid]) 
low=mid+1;
else return mid;
}
return 0;
}