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