第 08 章 基礎 約 12 分鐘
二分搜尋：猜數字遊戲的最佳策略
我在心裡想 1~100 的一個數字，你最少猜幾次保證猜中？答案是 7 次——這就是 O(log n)。
建議先看過： 02-big-o
猜數字遊戲
我想了一個 1~100 的數字，你猜，我會說「太大、太小、猜中」。最少幾次保證猜到？
你的本能應該是先猜 50——這是最聰明的猜法。
- 太大 → 答案在 1~49
- 太小 → 答案在 51~100
- 不管哪邊，範圍縮成一半
繼續玩這個遊戲，每次砍一半：100 → 50 → 25 → 13 → 7 → 4 → 2 → 1。 7 次保證猜中。
這 7 是怎麼來的？，向上取整 = 7。
💡這就是 O(log n)
每次砍一半 → O(log n)。 1024 筆資料只要 10 次、100 萬筆資料只要 20 次。
二分搜尋的前提
陣列必須先排好序！ 沒排好的話沒辦法「砍一半」——你不知道答案在哪一邊。
視覺化
在 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 中找 13：
Pseudocode
Algorithm BinarySearch(A, target):
left ← 0
right ← n - 1
while left ≤ right:
mid ← (left + right) / 2
if A[mid] == target:
return mid // 找到了
else if A[mid] < target:
left ← mid + 1 // 往右找
else:
right ← mid - 1 // 往左找
return -1 // 找不到
複雜度
| Big-O | |
|---|---|
| 時間 | O(log n) |
| 空間（迭代版） | O(1) |
| 空間（遞迴版） | O(log n) — 因為堆疊 |
跟線性搜尋 O(n) 比：
| n | 線性搜尋 (O(n)) | 二分搜尋 (O(log n)) |
|---|---|---|
| 100 | 100 次 | 7 次 |
| 1,000,000 | 1,000,000 次 | 20 次 |
| 10 億 | 10 億次 | 30 次 |
⚠️常見錯誤
- 忘記陣列要先排序——這是大前提。
mid = (left + right) / 2在某些語言會 overflow（如果 left + right 超過 int 範圍）。 實務寫成mid = left + (right - left) / 2。- 邊界條件：
left ≤ right還是left < right？跟你怎麼更新 left/right 有關。最常見的寫法是≤+mid+1/mid-1。
📝考試會這樣考
題型一：給陣列和目標，列出每一輪的 left/right/mid。
例：在 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] 中找 23，列出搜尋過程。
| 輪 | left | right | mid | A[mid] | 動作 |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 16 | 16 < 23，left = 5 |
| 2 | 5 | 9 | 7 | 56 | 56 > 23，right = 6 |
| 3 | 5 | 6 | 5 | 23 | 找到！ |
題型二：問最多需要幾次比較才能在 n 個元素中找到？ 答： 次（向上取整）。n = 1000 → 10 次。
題型三：問為什麼必須先排序？ 答：因為「砍一半」要靠「A[mid] 跟 target 比，能決定答案在左還右」的性質，沒排序這個性質就不成立。
這章記住
- 每次砍一半 → O(log n)。
- 前提：陣列必須先排好。
- 1 億筆資料只要找約 27 次——這就是為什麼資料庫的索引都用樹結構（後面會講）。
學習進度只存在你的瀏覽器，不會上傳。