隻有10%的程式員可以寫出二分查找算法！

有一些講程式設計的圖書，我會從頭到尾、一字不落地反複研讀；還有一些講程式設計的圖書，我已經看過好幾遍了，但每次差不多都是隻看其中的一章。喬恩·本特利（Jon Bentley）1986年的經典名著《程式設計珠玑》（Programming Pearls）則是少數幾本能同時歸入上述兩類的程式設計圖書之一。

隻有10%的程式員可以寫出二分查找

每次翻開《程式設計珠玑》，我都會先看一看下面這幾段文字： 

二分查找可以解決（預排序數組的查找）問題：隻要數組中包含T（即要查找的值），那麼通過不斷縮小包含T的範圍，最終就可以找到它。一開始，範圍覆寫整個數組。将數組的中間項與T進行比較，可以排除一半元素，範圍縮小一半。就這樣反複比較，反複縮小範圍，最終就會在數組中找到T，或者确定原以為T所在的範圍實際為空。對于包含N個元素的表，整個查找過程大約要經過log(2)N次比較。 

多數程式員都覺得隻要了解了上面的描述，寫出代碼就不難了；但事實并非如此。如果你不認同這一點，最好的辦法就是放下書本，自己動手寫一寫。試試吧。 

我在貝爾實驗室和IBM的時候都出過這道考題。那些專業的程式員有幾個小時的時間，可以用他們選擇的語言把上面的描述寫出來；寫出進階僞代碼也可以。考試結束後，差不多所有程式員都認為自己寫出了正确的程式。于是，我們花了半個鐘頭來看他們編寫的代碼經過測試用例驗證的結果。幾次課，一百多人的結果相差無幾：90%的程式員寫的程式中有bug（我并不認為沒有bug的代碼就正确）。

我很驚訝：在足夠的時間内，隻有大約10%的專業程式員可以把這個小程式寫對。但寫不對這個小程式的還不止這些人：高德納在《計算機程式設計的藝術 第3卷 排序和查找》第6.2.1節的“曆史與參考文獻”部分指出，雖然早在1946年就有人将二分查找的方法公諸于世，但直到1962年才有人寫出沒有bug的二分查找程式。 

——喬恩·本特利，《程式設計珠玑（第1版）》第35-36頁

幾個小時！90%！老兄，嚴肅點！難道這還不夠駭人聽聞嗎？

好，下面就做一個二分查找的測驗

我跟你一樣（如果你是這麼想的），想馬上就試一試。（好啦，不是馬上。先看完這篇文章！）我相信看這篇文章的人都知道什麼是二分查找算法，即使你不知道，上面引用的本特利的描述也應該夠了。請你打開編輯器，編寫一個二分查找例程。什麼時候覺得沒有任何問題了，保留那個版本。然後測試，然後通過在下面留言的方式告訴我你是不是第一次就做對了。我們肯定能打破本特利10%的紀錄嗎？

規則如下。

1.使用你喜歡的任何程式設計語言。

2.不要剪切粘貼或以任何方式複制别人的代碼。甚至在你寫完之前，都不要參考其他的二分查找代碼。

3.甚至于我不得不強調，别調用bsearch()，或使用其他瞞天過海的手法

4.時間自己來定：5分鐘不短——隻要你能保證寫完寫對；8小時不長——隻要你願意（而且有那麼多閑工夫）。

5.可以使用編譯器消除一些無意識的錯誤，如文法錯誤或變量初始化失敗，但……

6.在确定程式正确之前不要測試。 

7.最後，也是最重要的：如果決定參與這次測驗，就必須報告。成功也好，失敗也罷，甚至半途而廢也要給我個話兒。否則，就無法保證測驗結果的準确性了。

（考慮到這隻是一次測驗，可以忽略計算索引時導緻的數值溢出。這裡描述了相應的情形，但打算參加這次測驗的人在編完程式之前不要看，因為那篇文章裡包含一個正确的二分查找的實作，對自己能力有自信的朋友一定是不屑為之的。）

如果你的代碼經驗證确實正确，那麼如果你願意的話，歡迎你在留言裡貼出自己的代碼。不過，假如你這樣做了，而後來的留言給你挑出了bug，請你一定想好怎樣為維護自己的形象而自圓其說

更酷的玩法：對于那些信心十足的人，如果你真敢肯定自己的程式沒有問題，可以先把代碼貼在留言裡，然後再測試。當然，你必須要在留言裡說明這一點，以便大家發現你的bug時，會考慮多少給你留些情面。

我會在某個時間總結一下這次測試的結果——比如說，一周以後。

行動吧！