《程式設計珠玑（第2版•修訂版）》—第2章2.2節無處不在的二分搜尋

本節書摘來自異步社群《程式設計珠玑（第2版•修訂版）》一書中的第2章2.2節無處不在的二分搜尋，作者【美】jon bentley，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

2.2　無處不在的二分搜尋

我想到的一個數在1到100之間，你來猜猜看。50？太小了。75？太大了。如此，遊戲進行下去，直到你猜中我想到的數為止。如果我的整數位于1到n之間，那麼你可以在log2n次之内猜中。如果n是1 000，10次就可以完成；如果n是100萬，則最多20次就可以完成。

這個例子引出了一項可以解決衆多程式設計問題的技術：二分搜尋。初始條件是已知一個對象存在于一個給定的範圍内，而一次探測操作可以告訴我們該對象是否低于、等于或高于給定的位置。二分搜尋通過重複探測目前範圍的中點來定位對象。如果一次探測沒有找到該對象，那麼我們将目前範圍減半，然後繼續下一次探測。當找到所需要的對象或範圍為空時停止。

在程式設計中二分搜尋最常見的應用是在有序數組中搜尋元素。在查找項50時，算法進行如下探測。

衆所周知，二分搜尋程式要正确運作很困難。在第4章中我們将詳細研究其代碼。

順序搜尋在搜尋一個具有n個元素的表時，平均需要進行n/2次比較，而二分搜尋僅僅進行不超過log2n次的比較就可以完成。這在系統性能上會造成巨大的差異。下面的故事來自于《acm通訊》的執行個體研究“twa reservation system”。

我們有一個執行線性搜尋的程式，可以在1秒鐘内對一塊非常巨大的記憶體塊完成100次搜尋。随着網絡的增長，處理每條消息所需的平均cpu時間上升了0.3毫秒，這對我們來說是巨大的變化。我們發現問題的根源是線性搜尋。把程式改為使用二分搜尋以後，該問題消失了。

我在許多系統中也遇到過相同的問題。程式員在開始的時候使用簡單的順序搜尋資料結構，這在開始的時候通常都足夠快。當搜尋變得太慢的時候，對表進行排序并使用二分搜尋通常可以消除瓶頸。

但是二分搜尋的故事并沒有在快速搜尋有序數組這裡終止。roy weil将該技術應用于清理一個約1000行的輸入檔案，其中僅包含一個錯誤行。很不幸，肉眼看不出錯誤行。隻能通過在程式中運作檔案的一個（起始）部分并且觀察到離奇錯誤的答案來辨識，這将會花費幾分鐘的時間。他的前任調試人員試圖通過每次運作整個程式中的少數幾行程式來找出錯誤行，但隻在取得解決方案的道路上前進了一點點。weil是如何僅僅運作10次程式就找到罪魁禍首的呢？

經過前面的熱身，我們現在來攻克問題a。輸入為順序檔案（考慮錄音帶或磁盤——雖然磁盤可以随機讀寫，但是從頭至尾讀取檔案通常會快得多）。檔案包含最多40億個随機排列的32位整數，而我們需要找出一個不存在于該檔案中的32位整數。（至少缺少一個整數，因為一共有232也就是4 294 967 296個這樣的整數。）如果有足夠的記憶體，可以采用第1章中介紹的位圖技術，使用536 870 912個8位位元組形成位圖來表示已看到的整數。然而，該問題還問到在僅有幾百個位元組記憶體和幾個稀疏順序檔案的情況下如何找到缺失的整數？為了采用二分搜尋技術，就必須定義一個範圍、在該範圍内表示元素的方式以及用來确定哪一半範圍存在缺失整數的探測方法。如何來實作呢？

我們采用已知包含至少一個缺失元素的一系列整數作為範圍，并使用包含所有這些整數在内的檔案表示這個範圍。靈機一動的結果是通過統計中間點之上和之下的元素來探測範圍：或者上面或者下面的範圍具有至多全部範圍的一半元素。由于整個範圍中有一個缺失元素，是以我們所需的那一半範圍中必然也包含缺失的元素。這些就是解決該問題的二分搜尋算法所需要的主要想法。在翻閱答案檢視ed reingold是如何做的以前，請嘗試将這些想法組織起來。

對于二分搜尋技術在程式設計中的應用來說，這些應用僅僅是皮毛而已。求根程式使用二分搜尋技術，通過連續地對分區間來求解單變量方程式（數值分析家稱之為對分法）。當答案11.9中的選擇算法區分出一個随機元素以後，就對該元素一側的所有元素遞歸地調用自身（這是一種随機二分搜尋）。其他使用二分搜尋的地方包括樹資料結構和程式調試（當程式沒有任何提示就意外中止時，你會從源代碼中哪一部分開始探測來定位錯誤語句呢？）。在上述的每個例子中，分析程式并對二分搜尋算法做些許修改，可以帶給程式員功能強大的啊哈！靈機一動。