第二十五章：二分查找實(shí)現(xiàn)（Jon Bentley：90%程序員無(wú)法正確實(shí)現(xiàn)）
作者：July
出處：結(jié)構(gòu)之法算法之道
引言
Jon Bentley：90%以上的程序員無(wú)法正確無(wú)誤的寫(xiě)出二分查找代碼。也許很多人都早已聽(tīng)說(shuō)過(guò)這句話，但我還是想引用《編程珠璣》上的如下幾段文字：
“二分查找可以解決（預(yù)排序數(shù)組的查找）問(wèn)題：只要數(shù)組中包含T（即要查找的值），那么通過(guò)不斷縮小包含T的范圍，最終就可以找到它。一開(kāi)始，范圍覆蓋整個(gè)數(shù)組。將數(shù)組的中間項(xiàng)與T進(jìn)行比較，可以排除一半元素，范圍縮小一半。就這樣反復(fù)比較，反復(fù)縮小范圍，最終就會(huì)在數(shù)組中找到T，或者確定原以為T所在的范圍實(shí)際為空。對(duì)于包含N個(gè)元素的表，整個(gè)查找過(guò)程大約要經(jīng)過(guò)log(2)N次比較。
多數(shù)程序員都覺(jué)得只要理解了上面的描述，寫(xiě)出代碼就不難了；但事實(shí)并非如此。如果你不認(rèn)同這一點(diǎn)，最好的辦法就是放下書(shū)本，自己動(dòng)手寫(xiě)一寫(xiě)。試試吧。
我在貝爾實(shí)驗(yàn)室和IBM的時(shí)候都出過(guò)這道考題。那些專業(yè)的程序員有幾個(gè)小時(shí)的時(shí)間，可以用他們選擇的語(yǔ)言把上面的描述寫(xiě)出來(lái)；寫(xiě)出高級(jí)偽代碼也可以。考試結(jié)束后，差不多所有程序員都認(rèn)為自己寫(xiě)出了正確的程序。于是，我們花了半個(gè)鐘頭來(lái)看他們編寫(xiě)的代碼經(jīng)過(guò)測(cè)試用例驗(yàn)證的結(jié)果。幾次課，一百多人的結(jié)果相差無(wú)幾：90%的程序員寫(xiě)的程序中有bug（我并不認(rèn)為沒(méi)有bug的代碼就正確）。
我很驚訝：在足夠的時(shí)間內(nèi)，只有大約10%的專業(yè)程序員可以把這個(gè)小程序?qū)憣?duì)。但寫(xiě)不對(duì)這個(gè)小程序的還不止這些人：高德納在《計(jì)算機(jī)程序設(shè)計(jì)的藝術(shù) 第3卷 排序和查找》第6.2.1節(jié)的“歷史與參考文獻(xiàn)”部分指出，雖然早在1946年就有人將二分查找的方法公諸于世，但直到1962年才有人寫(xiě)出沒(méi)有bug的二分查找程序。”——喬恩·本特利，《編程珠璣（第1版）》第35-36頁(yè)。
你能正確無(wú)誤的寫(xiě)出二分查找代碼么？不妨一試。
二分查找代碼
二分查找的原理想必不用多解釋了，不過(guò)有一點(diǎn)必須提醒讀者的是，二分查找是針對(duì)的排好序的數(shù)組。OK，紙上讀來(lái)終覺(jué)淺，覺(jué)知此事要躬行。我先來(lái)寫(xiě)一份，下面是我寫(xiě)的一份二分查找的實(shí)現(xiàn)（之前去某一家公司面試也曾被叫當(dāng)場(chǎng)實(shí)現(xiàn)二分查找，不過(guò)結(jié)果可能跟你一樣，當(dāng)時(shí)就未能完整無(wú)誤寫(xiě)出），有任何問(wèn)題或錯(cuò)誤，懇請(qǐng)不吝指正：
//二分查找V0.1實(shí)現(xiàn)版
//copyright@2011 July
//隨時(shí)歡迎讀者找bug，email：zhoulei0907@yahoo.cn。
//首先要把握下面幾個(gè)要點(diǎn)：
//right=n-1 => while(left <= right) => right=middle-1;
//right=n => while(left < right) => right=middle;
//middle的計(jì)算不能寫(xiě)在while循環(huán)外，否則無(wú)法得到更新。
int binary_search(int array[],int n,int value)
{
int left=0;
int right=n-1;
//如果這里是int right = n 的話，那么下面有兩處地方需要修改，以保證一一對(duì)應(yīng)：
//1、下面循環(huán)的條件則是while(left < right)
//2、循環(huán)內(nèi)當(dāng)array[middle]>value 的時(shí)候，right = mid
while (left<=right) //循環(huán)條件，適時(shí)而變
{
int middle=left + ((right-left)>>1); //防止溢出，移位也更高效。同時(shí)，每次循環(huán)都需要更新。
if (array[middle]>value)
{
right =middle-1; //right賦值，適時(shí)而變
}
else if(array[middle]<value)
{
left=middle+1;
}
else
return middle;
//可能會(huì)有讀者認(rèn)為剛開(kāi)始時(shí)就要判斷相等，但畢竟數(shù)組中不相等的情況更多
//如果每次循環(huán)都判斷一下是否相等，將耗費(fèi)時(shí)間
}
return -1;
}