今天再次解決一個需要使用二分查找的問題,再一次的,我又沒有一次過寫對.(為什么我說"又"?)
抓狂了,似乎開始有一些"二分查找恐懼癥".
為了以后能夠一次將這個基本的算法寫對,我決定再仔細研究一下.我之前有寫過一個二分查找的算法,在
這里,這一次再以這個問題為例來說明.
我今早寫下的錯誤代碼類似于下面的樣子:
#include <stdio.h>
int search(int array[], int n, int v)
{
int left, right, middle;
left = 0, right = n;
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 main()
{
int array[] = {0, 1, 2, 3, 4, 5, 6, 7, 13, 19};
int m = search(array, sizeof(array)/sizeof(array[0]), 1);
printf("m = %d\n", m);
return 0;
}
實際上,如果使用測試用例來測試,這個算法并不是在所有情況下都會出錯的,還是有時可以得到正確的結果的.但是,你能看出來它錯在哪兒嗎?
在這里,循環的開始處,把循環遍歷的序列區間是這樣的:
left =0, right = n;
while (left < right)
{
// 
循環體
}
也就是說,這是一個左閉右開的區間:[0, n).
但是,在循環內部, 卻不是這樣操作的:
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle - 1;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
當array[middle] > v條件滿足時, 此時v如果存在的話必然在左閉右開區間[left, middle)中, 因此,當這個條件滿足時, right應該為middle, 而在這里, right賦值為middle - 1了, 那么, 就有可能遺漏array[middle - 1] = v的情況.
因此,這種錯誤的寫法并不是在所有的情況下都會出錯,有時還是可以找到正確的結果的.
這是一種典型的二分查找算法寫錯的情況,循環體是左閉右開區間,而循環體內部卻是采用左閉右閉區間的算法進行操作.
下面給出的兩種正確的算法,算法search是左閉右閉區間算法,而算法search2是左閉右開區間算法,可以對比一下差異.
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 search2(int array[], int n, int v)
{
int left, right, middle;
left = 0, right = n;
while (left < right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}
return -1;
}
下面再給出另一種典型的錯誤的二分查找算法,當查找的元素不在序列內時,它可能造成程序的死循環.
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;
}
else if (array[middle] < v)
{
left = middle;
}
else
{
return middle;
}
}
return -1;
}
為什么會造成死循環?
從循環條件來看,這個算法的操作區間是左閉右閉區間的,因此當array[middle] > v時,v如果存在的話應該在[left, middle- 1]中,因此此時right應該是middle - 1,而不是middle;類似的,當array[middle] < v時,下一次操作的區間應該是[middle + 1, right]中.而當元素不存在這個序列中時,算法在一個錯誤的區間中循環,但是又不能終止循環,于是就造成了死循環.
因此,要將二分查找算法寫對,其實很多人都大概知道思想,具體到編碼的時候,就會被這些看似微小的地方搞糊涂.因此,需要注意這一點:
算法所操作的區間,是左閉右開區間,還是左閉右閉區間,這個區間,需要在循環初始化,循環體是否終止的判斷中,以及每次修改left,right區間值這三個地方保持一致,否則就可能出錯.