意義與機制
循序搜尋依次檢查數值，二分搜尋則檢查目前區間的中間值。判斷目標值較大或較小後，可利用排序關係排除其中一側。
每次比較後，都必須保持以下條件：如果目標值存在，它就位於剩餘區間內。區間為空時，便可得出目標值不存在的結論。
關係與條件
候選人數大約隨著 n/2ᵏ 減少，因此比較次數呈對數增長。對於模擬中的無重複列表，當 n ≥ 1 時，最大比較次數可以與 ⌊log₂n⌋ + 1 進行比較。
排序的成本必須與搜尋成本分開考慮。當解決在包含重複值的列表中找到第一個和最後一個位置的問題時，必須調整停止條件。
觀察實驗中需要注意的事物
二分搜尋在每次探測時，將候選範圍減半。
排序後的整數列表沒有重複元素。 兩種方法使用相同的列表。
關鍵關係與符號
binary steps ≤ ⌊log₂n⌋ + 1
| 符號 | 含義 | 單位 |
|---|---|---|
| n | 資料項數量 | 個 |
| k | 比較次數與範圍減少量 | 次 |
透過範例確認
二分搜尋需要什麼？
排序列表 · 二分搜尋在每次查詢時，將候選範圍減半。
常見誤解
- 對未排序的串列只套用中間值比較規則，無法得到正確的二分搜尋。