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