二分搜尋作為分治法（binary search）

在紙本字典裡查一個字，你不會從第一頁開始；你翻到中間，看你的字在它之前或之後，然後丟掉不可能含有它的那一半。在剩下的那半重複。二分搜尋正是把這個想法用在已排序的陣列上：檢查中間元素，一次比較就能淘汰一半的剩餘候選。

精確地說：要在已排序陣列 A[lo..hi] 中找 x，算出中點 m。若 A[m] 等於 x，就完成了。若 x < A[m]，答案只可能在左半，於是對 A[lo..m-1] 遞迴；若 x > A[m]，對 A[m+1..hi] 遞迴。區間持續縮小，直到變空（x 不存在）或落在 x 上。正確性可用迴圈不變量論證：若 x 在陣列中任何位置，它一定落在目前的 [lo..hi] 視窗內。開始時成立（視窗是整個陣列），每一步只丟掉一個已證明不含 x 的半段所以仍成立，迴圈在視窗剩一個元素（找到）或變空（不存在）時結束。這是一種退化的分治法：它分成兩半卻只征服其中一半，且不需要合併步驟。

因為每一步都把搜尋空間減半，二分搜尋以 O(log n) 執行——對一百萬筆資料，約 20 次比較。這種對數速度正是已排序結構如此珍貴的原因，也支撐了下界／上界查詢、用二分法求平方根與方程式根、以及任何單調述詞（對答案做二分搜尋）。不可妥協的前置條件：陣列必須已依你比較的鍵排好序。對未排序資料跑二分搜尋，它會理直氣壯地回傳錯誤答案，因為它丟掉的那半，可能正是目標所在之處。