猜數字

同一個問題，笨方法要一百次，聰明方法只要七次。 · ⏱ 約 30 分鐘

你會學到三件事

1. 同一個問題有很多種解法，而它們的代價差很多
2. 二分搜：每猜一次，範圍就少一半
3. 「要跑幾次」這件事本身可以被計算

開始之前

這一課沒有新的語法。你已經會的東西剛好夠了： 變數、while、if、比較。

而它是整個課程的轉折——在這之前你在學怎麼講， 從這裡開始你要學講什麼。

一、笨方法

猜一個 1 到 100 的數字。從 1 開始一個一個試：

int guess = 1;
while (guess != target) {
    guess = guess + 1;
}

它一定猜得到。而如果答案是 100，你要猜 100 次。

二、聰明方法

改成每次都猜範圍的正中間：

int lo = 1, hi = 100;
int mid = (lo + hi) / 2;    // 50

猜 50，然後：

每猜一次，可能的範圍就少一半。

100 → 50 → 25 → 13 → 7 → 4 → 2 → 1
 ①    ②    ③    ④   ⑤   ⑥   ⑦

七次。而笨方法最多一百次。

三、七這個數字是算得出來的

範圍每次砍一半，砍幾次會剩下 1？

100 ÷ 2 ÷ 2 ÷ 2 ÷ 2 ÷ 2 ÷ 2 ÷ 2 ≈ 0.78
      ①   ②   ③   ④   ⑤   ⑥   ⑦

也就是「2 要乘幾次才會超過 100」——答案是 7（2⁷ = 128）。

推廣一下：

範圍變成一萬倍，二分搜只多了 23 次。

這就是「複雜度」在講的事：不是「快多少」， 是「資料變大的時候，它變慢的速度」。

四、寫出來

int lo = 1, hi = 100, steps = 0;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    steps = steps + 1;
    if (mid == target) break;
    if (mid < target) lo = mid + 1;
    else hi = mid - 1;
}

⚠️ 三個很容易寫錯的地方：

1. lo <= hi 不是 lo < hi——寫成 < 的話，範圍剩一個數字時就不猜了
2. mid - 1 和 mid + 1 的那個 1 不能省——mid 已經猜過了， 不排掉它會變成無窮迴圈
3. (lo + hi) / 2 是整數除法（第 5 課），小數會被丟掉——而這裡正好是我們要的

完成的樣子

int main() {
    int target = 42;
    int lo = 1, hi = 100, steps = 0;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        steps = steps + 1;
        if (mid == target) break;
        if (mid < target) lo = mid + 1;
        else hi = mid - 1;
    }
    cout << "猜了 " << steps << " 次" << endl;
    return 0;
}

換你了

把 target 換成 1、換成 100、換成 63，看看各要幾次。

最多是幾次？ 試出那個最壞的情況——它應該是 7。

這一課你做了什麼

• 你寫出了兩種解同一個問題的方法
• 你看到範圍一萬倍、次數只多 23 次
• 你第一次計算了「一個做法要跑幾次」

如果卡住了