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