Learning Objectives
- 寫出線性搜尋，說明最壞情況要比較 n 次
- 說明二分搜尋的前提是資料已經排序，並追蹤 lo、hi、mid 在每一輪怎麼移動
- 說明二分搜尋每一輪排除一半，所以最多只要比較約 log₂n 次
- 分辨「找到某個值」和「找第一個大於等於某值的位置」（lower_bound），正確寫出邊界條件
- 使用 Python、C++、Java 內建的二分搜尋工具
在一排資料裡找東西
「學號 1123 在不在名單上？」「價格 300 元的商品排在第幾個？」這類問題叫做搜尋（search）：給一組資料和一個目標值，找出目標在哪裡，找不到就回報找不到。
最直接的做法是從頭開始一個一個看，這叫線性搜尋（linear search）：
- 從第 0 個元素開始
- 和目標相等就回傳目前的位置
- 否則看下一個；全部看完都沒有，就回傳 -1
這一課的每個範例都有 Python、C++、Java 三種寫法，可以用動畫上方的按鈕切換；選擇會記在瀏覽器裡，整頁一起換。 三種寫法的輸出完全相同，差別只在語法。
線性搜尋：一個一個比
上方的格子是陣列 a，▲ 標出迴圈變數 i 指到的位置。找 61 時比到第 5 個才找到；找 50 時把 7 個元素全部比完才確定不在裡面。
線性搜尋要比幾次
比較的次數取決於目標在哪裡：
| 情況 | 比較次數 |
|---|---|
| 最好：目標就在第一個 | 1 |
| 最壞：目標在最後一個，或根本不在陣列裡 | n |
| 平均（目標在每個位置的機會相同） | 約 n / 2 |
分析演算法時通常看最壞情況，因為它保證「再慢也不會超過這樣」。線性搜尋的最壞情況是 n 次，資料量變成 10 倍，比較次數也變成 10 倍，用第 02 課的寫法就是 O(n)。
線性搜尋的好處是不挑資料：沒有排序、甚至是一邊讀一邊找都可以。但如果資料已經排好順序，就有快得多的方法。
二分搜尋：每次排除一半
翻字典找「演算法」這個詞，不會從第一頁開始翻。你會先翻到中間，看那一頁的字比目標前面還是後面，再決定往哪一半找。這就是二分搜尋（binary search）的想法。
前提：陣列必須已經由小到大排好。做法是用兩個索引 lo、hi 圍出「目標如果存在，一定在這個範圍裡」：
- 一開始
lo = 0、hi = n - 1，範圍是整個陣列 - 取中間
mid = (lo + hi) / 2（整數除法） a[mid]剛好等於目標：找到了a[mid]比目標小：目標只可能在右半邊，lo = mid + 1a[mid]比目標大：目標只可能在左半邊，hi = mid - 1- 只要
lo <= hi範圍裡就還有元素，回到第 2 步；lo > hi表示範圍空了，目標不在陣列裡
第 4、5 步寫成 mid + 1、mid - 1 而不是 mid，因為 a[mid] 已經比過、確定不是目標了，下一輪不需要再把它算進範圍。
二分搜尋：看 lo、mid、hi 怎麼移動
灰掉的格子已經不在搜尋範圍裡。找 63 時，第一輪看正中間的 34，比 63 小，左半邊整段被排除；第三輪就找到了。找 30 時，範圍縮到 lo > hi（範圍空了），回傳 -1。12 個元素最多只要比 4 次。
為什麼這麼快：對半再對半
每比一次，範圍就剩下一半（甚至更少）。n 個元素要對半切幾次才會只剩 1 個？
| 元素個數 n | 最多比較次數 |
|---|---|
| 10 | 4 |
| 1,000 | 10 |
| 1,000,000 | 20 |
| 1,000,000,000 | 30 |
規律是：n 每變成 2 倍，次數只多 1。這個次數大約是 log₂n（2 要乘幾次才會超過 n），所以二分搜尋是 O(log n)。 十億筆資料，線性搜尋最壞要比十億次，二分搜尋只要約 30 次。
下面的程式模擬「猜數字」的最壞情況：每次猜正中間，而且每次都猜得太小，數一數總共猜了幾次。
數一數要猜幾次
看上方 lo 和 hi 的距離，每一輪大約縮成一半。n 從 1,000 變成 1,000,000（變成 1000 倍），次數只從 10 變成 20。
想一想：二分搜尋的前提與次數
對陣列 [30, 10, 50, 20, 40] 用二分搜尋找 20，會怎樣？
一個已排序的陣列有 4,000 個元素，二分搜尋最多要比較幾次？
把二分搜尋的迴圈條件 while lo <= hi 改成 while lo < hi（其他不變），會發生什麼事？
找「第一個大於等於」的位置
二分搜尋找到的是「某一個」等於目標的位置。陣列裡有重複值時，例如 [10, 20, 20, 20, 30, 40] 找 20，回傳的可能是 1、2、3 任何一個，取決於 mid 先落在哪裡。
實際應用常問的是另一個問題：第一個 ≥ 目標的位置在哪裡？ 這叫 lower_bound，它有幾個好用的性質：
- 目標存在時，回傳的是第一次出現的位置
- 目標不存在時，回傳的是「把目標插進去、陣列仍然有序」的位置
- 所有元素都比目標小時，回傳 n（陣列的長度）
寫法改用半開區間 [lo, hi)：含 lo、不含 hi。hi 從 n 開始（n 本身也是可能的答案），迴圈條件是 lo < hi：
a[mid] < target：mid 和它左邊都不是答案，lo = mid + 1- 否則
a[mid] >= target：mid 可能就是答案，所以hi = mid（不是mid - 1）
迴圈結束時 lo == hi，這就是答案。
lower_bound：重複值與不存在的值
找 20 時，即使 a[mid] 已經等於 20，hi 還是會繼續往左縮，因為左邊可能還有 20；最後停在第一個 20，索引 1。找 25 得到 4（25 應該插在 20 和 30 之間）；找 99 得到 6，也就是陣列長度。hi 等於 6 時已經超出最後一格，所以標在格子下方的文字裡。
各語言內建的二分搜尋
實際寫程式時，通常直接用語言內建的工具，不必自己寫：
| 語言 | 寫法 | 回傳 |
|---|---|---|
| Python | bisect.bisect_left(a, x) |
第一個 ≥ x 的位置（就是 lower_bound） |
| Python | bisect.bisect_right(a, x) |
第一個 > x 的位置 |
| C++ | lower_bound(a.begin(), a.end(), x) |
指向第一個 ≥ x 的迭代器，減掉 a.begin() 得到索引 |
| C++ | binary_search(a.begin(), a.end(), x) |
只回傳 true／false |
| Java | Arrays.binarySearch(a, x) |
找到時回傳某一個相等元素的索引；找不到時回傳負數 -(插入位置) - 1 |
注意 Java 的 Arrays.binarySearch 遇到重複值時，不保證回傳第一個；需要第一次出現的位置，要自己寫 lower_bound。
自己寫二分搜尋最常出錯的地方是邊界：用閉區間 [lo, hi] 還是半開區間 [lo, hi)、迴圈條件用 <= 還是 <、更新時用 mid 還是 mid ± 1。
選定一種區間，三個地方就要一致。
另外，C++ 與 Java 的 int 有上限（約 21 億）。陣列非常大時，lo + hi 可能超過上限而溢位變成負數，所以範例寫成 lo + (hi - lo) / 2，結果相同但不會溢位。Python 的整數沒有上限，不會有這個問題。
想一想：lower_bound 的結果
a = [2, 4, 4, 4, 7, 9]，lower_bound(a, 4) 和 lower_bound(a, 5) 分別是多少？
已排序的陣列裡，怎麼用 lower_bound 算出「值 x 出現了幾次」？
實作：一個分數出現幾次
scores 是由小到大排好的成績。請完成 lower_bound（第一個 ≥ target 的位置），再用它算出 80 分、85 分、100 分各有幾個人。預期輸出在右邊；可以切換成你熟悉的語言。
重點整理
- 線性搜尋一個一個比，不需要排序，最壞要比 n 次，O(n)
- 二分搜尋要求資料已經排序，每一輪排除一半，最多約 log₂n 次，O(log n)
- 閉區間
[lo, hi]配while lo <= hi、lo = mid + 1、hi = mid - 1；半開區間[lo, hi)配while lo < hi、hi = mid - lower_bound 找第一個 ≥ 目標的位置：目標存在時是第一次出現的位置，不存在時是應該插入的位置
- C++、Java 用
lo + (hi - lo) / 2避免lo + hi溢位
下一課：遞迴。二分搜尋也可以用遞迴寫，到時候會看到「把問題切成一半」的另一種寫法。