本節書摘來自異步社區《編程珠璣（第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中的選擇算法區分出一個隨機元素以后，就對該元素一側的所有元素遞歸地調用自身（這是一種隨機二分搜索）。其他使用二分搜索的地方包括樹數據結構和程序調試（當程序沒有任何提示就意外中止時，你會從源代碼中哪一部分開始探測來定位錯誤語句呢？）。在上述的每個例子中，分析程序并對二分搜索算法做些許修改，可以帶給程序員功能強大的啊哈！靈機一動。