Bentley在他的著作《Writing Correct Programs》中寫道，90%的計(jì)算機(jī)專家不能在2小時內(nèi)寫出完全正確的二分搜索算法。
我自己嘗試了一下,確實(shí)要第一次就完全寫正確不容易.以下兩份實(shí)現(xiàn)依次為迭代和遞歸版本的代碼,二分查找的思想很多人都清楚,但是這里有一個細(xì)節(jié)就是要注意邊界的選擇.
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;
}