Bentley在他的著作《Writing Correct Programs》中写道，90%的计较机专家不能在2小时内写出完全正确的二分搜索算法。
我本身实验了一下,确实要第一次就完全写正确不容易.以下两份实现依次为迭代和递归版本的代码,二分查找的思想许多人都清楚,可是这里有一个细节就是要留意界线的选择.
int search(int array[],int n,int v)
{
int left,right,middle;
left = 0,right = n - 1;
while (left <= right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle - 1;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}
return -1;
}
int search_recurse(int array[],int low,int high,int v)
{
int middle;
middle = (low + high) / 2;
if (low < high)
{
if (array[middle] > v)
{
return search_recurse(array,low,middle,v);
}
else if (array[middle] < v)
{
return search_recurse(array,middle + 1,high,v);
}
else
{
return middle;
}
}
else if (low == high)
{
if (array[middle] == v)
{
return middle;
}
else
{
return -1;
}
}
else
{
return -1;
}
return -1;
}
int main()
{
int array[] = {0,1,2,3,4,5,6,7,13,19};
int m = search(array,sizeof(array)/sizeof(array[0]),13);
printf("m = %d\n",m);
m = search_recurse(array,0,sizeof(array)/sizeof(array[0]),13);
printf("m = %d\n",m);
return 0;
}
