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