二分搜索法每次将搜索空间缩小一倍,其最大搜索长度为:log[n]+1
bool binarySearch(int target,int tmpArr[],int length)
{
int l,u,m;
l=0;
u=length-1;
while(l<=u)
{
m=(l+u)/2;
if(tmpArr[m]>target)u=m-1;
else if(tmpArr[m]==target)return true;
else l=m+1;
}
return false;
}
测试程序:
#include <iostream.h>
void swap(int &a,int &b);
void simpleSort(int tmpArr[],int length);
void showArr(int tmpArr[],int length);
bool binarySearch(int target,int tmpArr[],int length);
int main()
{
int arr[10]={8,7,5,4,2,3,10,11,21,87};
int len=10;
int target=4;
simpleSort(arr,len);
showArr(arr,len);
if(binarySearch(target,arr,len))
cout<<"target:"<<target<<"was found."<<endl;
else
cout<<"target:"<<target<<"was not found."<<endl;
return 1;
}
void swap(int &a,int &b)
{
int tmp=a;
a=b;
b=tmp;
}
void simpleSort(int tmpArr[],int length)
{
int i=0,j=0;
for(i=length-1;i>0;i--)
for(j=0;j<i;j++)
if(tmpArr[j]>tmpArr[j+1])swap(tmpArr[j],tmpArr[j+1]);
}
void showArr(int tmpArr[],int length)
{
cout<<"[";
int i=0;
for(;i<length-1;i++)
cout<<tmpArr[i]<<",";
cout<<tmpArr[length-1]<<"]"<<endl;
}
