搜尋：線性 vs 二分

線性搜尋：全部查一遍，O(n)

在陣列裡找一個值，最顯然的辦法是從第一格到最後一格、挨個查看，一找到就停。這就是[[linear-search|線性搜尋]]，它永遠有效——哪怕在一串雜亂無序的串列上也行。代價是：最壞情況下（值在最後，或根本不存在），你要查遍全部 *n* 項，所以它是 O(n)。資料翻倍，工作量翻倍。它簡單又誠實，對於小的或無序的資料，它恰恰是對的工具。

#include <vector>

// Return the index of target in v, or -1 if not present.
int linearSearch(const std::vector<int>& v, int target) {
    for (int i = 0; i < v.size(); i++) {  // check each slot in turn
        if (v[i] == target) return i;     // found it -> done
    }
    return -1;                            // walked the whole array, absent
}

線性搜尋走一遍，命中就提前停。最壞情況要碰遍全部 n 個元素——O(n)。它完全不需要排序。

但線性搜尋白白浪費了一份禮物。如果資料恰好是已排序的，每一次比較告訴你的就不只是「不是這個」——它還告訴你目標必定在哪個*方向*。線性搜尋對此視而不見。下面的想法，正好撲上去抓住它。

二分搜尋：每次都減半，O(log n)

畫面是這樣的：你在一本真正的紙本詞典裡查一個單字。你不會從第 1 頁開始。你翻到*中間*，看看你的詞在前還是在後，一下子就扔掉半本書。然後在剩下的那一半上再來一次，再來一次——每翻一次，問題就一分為二。這就是[[binary-search|二分搜尋]]，而它之所以有效，全因為詞典是已排序的。排序是入場費；減半是回報。

search for 23 in a SORTED array (lo, hi mark the live range):

  index:   0    1    2    3    4    5    6
         [  3 |  8 | 15 | 23 | 42 | 56 | 91 ]
           lo            mid              hi      mid=3 -> v[3]=23 ?

  step 1: lo=0, hi=6, mid=3, v[mid]=23 == 23  -> FOUND at index 3!

  (if we'd wanted 8: 23>8 so drop the right half -> hi=mid-1=2,
   then mid=1, v[1]=8 -> found.  each step throws away half.)

看中間；一次比較就丟掉半個陣列。n -> n/2 -> n/4 -> …… 約 log₂(n) 步就縮到 1——這就是 O(log n)。

為什麼減半這麼厲害？從 *n* 出發，你走 *n → n/2 → n/4 → ……* 直到只剩一項。所需的減半次數就是 log₂(n)——而它增長得慢得驚人。一百萬項？大約 20 步。十億項？大約 30 步。拿它和線性搜尋的一百萬、十億步比一比。大O那一篇的那張回報表，*這一刻*成了真。

一個正確的二分搜尋，以及它為何有效

二分搜尋出了名地容易寫得*差一點點*對。我們保留兩個標記 `lo` 和 `hi`，把*仍可能含有*目標的那段範圍圈起來。我們看中間，然後挪動那個能讓範圍朝答案收窄的標記。請留意那個微小卻要命的細節：當我們越過中間時，我們挪到 `mid + 1` 或 `mid - 1`，絕不挪回 `mid`——否則範圍可能永遠不收窄，迴圈會無休止地空轉。

#include <vector>

// v MUST be sorted ascending. Returns an index of target, or -1.
int binarySearch(const std::vector<int>& v, int target) {
    int lo = 0, hi = (int)v.size() - 1;
    while (lo <= hi) {                 // while the range is non-empty
        int mid = lo + (hi - lo) / 2;  // midpoint (avoids overflow)
        if (v[mid] == target)      return mid;     // hit
        else if (v[mid] < target)  lo = mid + 1;   // target is to the right
        else                       hi = mid - 1;   // target is to the left
    }
    return -1;                         // range emptied -> not present
}

用 lo + (hi - lo) / 2，而不是 (lo + hi) / 2，這樣在巨大陣列上和也不會溢位。lo <= hi 讓空範圍這件事老實可靠。挪到 mid±1 保證每一步範圍都收窄。

我們怎麼*知道*它是對的，而不只是看上去合理？靠一個[[loop-invariant|迴圈不變量]]——一句在迴圈之前為真、且每走一趟之後依然為真的陳述。它是這樣的：*如果目標真在陣列裡，它的索引就落在 `[lo, hi]` 之內。* 開頭時它為真（範圍就是整個陣列）。每一步只丟掉我們已*證明*不可能含有目標的那一半，所以它保持為真。當迴圈以 `lo > hi` 結束時，範圍空了——而既然不變量一直成立，目標就確實不在那裡。這個不變量，是從「看著對」通往「就是對」的橋。