[算法,分治]二分搜索法

二分搜索法每次将搜索空间缩小一倍,其最大搜索长度为: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;

}