什麼是二分搜尋
在已排序的資料中，與中央元素比較，每次把搜尋範圍縮小一半的搜尋方法。從 n 個資料中最多以 ⌊log₂ n⌋ + 1 次比較找到，時間複雜度為 O(log n)。前提是資料已排序。
日文名稱: 二分探索
「二分搜尋」出現在3領域的7道練習題中（資料結構與演算法, AD/DA轉換, 軟體開發與專案管理等）。
這個名詞所屬的領域: 資料結構與演算法
練習二分搜尋的題目
與陣列中央的元素比較、每次將搜尋範圍縮小一半的二分搜尋，其使用的前提條件為下列何者？
- A資料的個數是2的冪次
- B資料依鍵的順序排序
- C資料中不含相同的值
以二分搜尋在依升冪排序的1,000個不同值中尋找某個值。若1次比較就能得知「相等、較小、較大」，包含找得到與找不到的情況，比較次數最多為幾次？
- A10次
- B32次
- C500次
解析中的「二分搜尋」
二分搜尋依與中央元素比較的結果，判斷目標值在前半還是後半，將範圍減半。
與陣列中央的元素比較、每次將搜尋範圍縮小一半的二分搜尋，其使用的前提條件為下列何者？不過，二分搜尋需要資料已排序，也必須考慮排序所需的 O(n log n) 工作量。
以二分搜尋在依升冪排序的1,000個不同值中尋找某個值。若1次比較就能得知「相等、較小、較大」，包含找得到與找不到的情…若從舊的開始一個一個測試，最差要999次、平均也約500次，因此二分搜尋的效果很大。
在已知可正常運作的韌體版本之後有1,000個提交，最新的提交會發生缺陷。假設缺陷是由某1個提交引入，其後的提交全都會發…逐次逼近式從最高位元開始依序比較「輸入是否大於內部DAC的輸出」，像二分搜尋一樣逐位元決定。
關於逐次逼近式（SAR式）ADC的動作，下列何者正確？SAR式ADC從最高位元開始依序將內部DAC的電壓與輸入比較，以一次決定一位元的二分搜尋進行，因此N位元基本上需要N次比較。
N位元逐次逼近式ADC在一次轉換中進行的比較次數，基本上正確的是下列何者？
出現「二分搜尋」的題目（7題）
- 與陣列中央的元素比較、每次將搜尋範圍縮小一半的二分搜尋，其使用的前提條件為下列何者？
- 以二分搜尋在依升冪排序的1,000個不同值中尋找某個值。若1次比較就能得知「相等、較小、較大」，包含找得到與找不到的情況，比較次數最多為幾次？
- 以二分搜尋在依升冪排列的陣列 a[0]～a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60 中尋找38。搜尋範圍從下端 lo = 0、上端 hi = 9 開始，中央位置為 (lo + hi) ÷ 2 無條件捨去。依序排列與38比較的元素值，下列何者正確？
- 在已知可正常運作的韌體版本之後有1,000個提交，最新的提交會發生缺陷。假設缺陷是由某1個提交引入，其後的提交全都會發生。像 git bisect 那樣以二分搜尋找出原因提交時，需要建置並測試的次數最多為下列何者？
- 關於逐次逼近式（SAR式）ADC的動作，下列何者正確？
- N位元逐次逼近式ADC在一次轉換中進行的比較次數，基本上正確的是下列何者？
- 以從開頭逐一比較的線性搜尋，在存有100個不同值的陣列中尋找目標值。若目標值一定在陣列中，且位於各位置的機率相等，則比較次數的平均為多少？