它指的是將元素的集合為兩半，並在算法的每一步扔掉它們中的一個。這樣可以大大減少查找元素所需的比較次數。但是有一個陷阱，必須首先對集合中的元素進行排序。
其背後的想法類似於在書中查找頁面的步驟。首先，您通常將書打開到一個完全隨機的頁面，或者至少打開一個與您認為所需頁面可能接近的頁面。
有時，您很幸運可以在第一次嘗試時找到該頁面。但是，如果頁碼太少，則說明該頁必須在右側。如果您在下次嘗試時過衝，並且當前頁碼高於您要查找的頁碼，那麼您可以確定它必須介於兩者之間。
您重複此過程，但是要檢查位於該新範圍中間的頁面，而不是隨機選擇頁面。這樣可以最大程度地減少嘗試次數。
注意：有時，如果值是均勻分布的，則可以使用線性插值來計算中間索引，而不是取平均值。算法的這種變化將需要更少的步驟。
第一次嘗試時，中間的元素恰好是檸檬。由於它比草莓大，因此可以丟棄右邊的所有元素，包括檸檬。您將頁碼上限移動到新位置並更新中間索引：
限制要搜索的頁面範圍的頁碼稱為下限和上限。在二進位搜索中，通常以第一頁作為下界，最後一頁作為上限。必須在運行時更新兩個邊界。例如，如果您所翻的頁面低於您要查找的頁面，則這是您的新下限。
假設您要在按大小升序排列的一系列水果中尋找草莓：
第一次嘗試時，中間的元素恰好是檸檬。由於它比草莓大，因此可以丟棄右邊的所有元素，包括檸檬。您將頁碼移動到新位置並更新中間索引：
現在，您只剩下開始時所用水果的一半。當前的中間元素確實是您要尋找的草莓，搜索結束了。如果不是，那麼您將相應地更新邊界並繼續直到它們彼此通過。例如，尋找在草莓和奇異果之間缺失的李子，將得到以下結果：
請注意，為了找到所需的元素，並不需要進行很多比較。這就是二進位搜索的魔力。即使您要處理一百萬個元素，您最多只需要進行少量檢查。由於減半，該數字不會超過元素總數的對數底數2。換句話說，在每個步驟中剩餘元素的數量減少了一半。
這是可能的，因為元素已經按大小排序。但是，如果您想通過其他鍵（例如顏色）找到水果，則必須再次對整個集合進行排序。為了避免排序的開銷，您可以嘗試預先計算同一集合的不同視圖。這有點類似於創建資料庫索引。
考慮如果添加，刪除或更新集合中的元素會發生什麼。為了使二進位搜索繼續工作，您需要保持正確的排序順序。這可以通過該bisect模塊來完成，您將在接下來的部分中閱讀該模塊。
文章中，您將看到如何在Python中實現二進位搜索算法。現在，讓我們面對IMDb數據集。請注意，搜索的人與以前不同。這是因為必須對數據集進行排序以進行二進位搜索，從而對元素進行重新排序。新元素的位置大致與以前相同，以保持測量的可比性：
答案幾乎是即時的。通常情況下，二進位搜索只需要幾微秒的時間就可以找到全部900萬個元素中的一個！除此之外，所選元素的比較次數幾乎保持不變，這與以下公式一致：
查找大多數元素將需要最多數量的比較，這可以從集合大小的對數得出。相反，只有一次比較時，中間只有一個元素可以找到。
二進位搜索是分而治之技術的一個很好的例子，該技術將一個問題劃分為許多同類的較小問題。然後將各個解決方案合併以形成最終答案。這種技術的另一個眾所周知的例子是快速排序算法。
注意：不要將分治法與動態編程混淆，動態編程是一種有點類似的技術。
與其他搜索算法不同，二進位搜索不僅可以使用搜索，還可以使用。例如，它允許進行集合成員資格測試，找到最大值或最小值，找到目標值的最近鄰居，執行範圍查詢等等。
如果速度是頭等大事，那麼二進位搜索並不總是最佳選擇。甚至有更快的算法可以利用基於散列的數據結構。但是，這些算法需要大量額外的內存，而二進位搜索提供了很好的解決方案。