二分搜

排好序之後，找東西只要 log n 次。 · ⏱ 約 30 分鐘

你會學到三件事

1. lower_bound 找「第一個不小於 x 的位置」
2. 減掉 begin() 就變成索引
3. 二分搜的對象不一定是陣列

開始之前

C++ 入門第 12 課你自己寫過二分搜。這一課用標準函式。

⚠️ 前提是已經排好序。 沒排的話它給的答案是錯的，而且不會報錯。

🟢 先把編輯器打開，跟著下面一起做：跟著做

一、lower_bound

在已經排好的序列上找位置：

1vector<int> v = {1, 3, 5, 7, 9};2int idx = lower_bound(v.begin(), v.end(), 5) - v.begin();3cout << idx << endl;      // 2

lower_bound(範圍, x) 回傳「第一個 ≥ x 的位置」。

積木盤上它寫著「在 … 到 … 中找不小於 … 的第一個位置」 ——「不小於」就是 ≥。

減掉 begin() 就從「位置」變成「第幾個」：

v:      1    3    5    7    9
索引:   0    1    2    3    4
                 ▲
         lower_bound(…, 5) 指這裡 → 減 begin() = 2

二、兩個，差一格

有重複的時候差別就出來了：

v:      1    3    3    3    5
              ▲              ▲
        lower(3)          upper(3)

所以 upper_bound(3) - lower_bound(3) 就是 3 出現幾次，不用自己數。

三、⚠️ 找不到的時候

lower_bound 永遠會回一個位置，即使 x 不在裡面。

1auto it = lower_bound(v.begin(), v.end(), 4);2// 指向 5 的位置——因為 5 是第一個 ≥ 4 的

auto 是「讓編譯器自己看右邊是什麼型別」—— 積木盤上那一顆的型別格子選「自動推斷」就是它。

所以「有沒有」要自己檢查兩件事：

1int i = lower_bound(v.begin(), v.end(), x) - v.begin();2if (i < v.size() && v[i] == x) {3    // 找到了4}

⚠️ 兩個條件的順序不能反，這是第 1 課的短路： i 可能等於 v.size()，那時 v[i] 是越界的。

四、🔴 二分搜的對象不一定是陣列

這是這一課真正重要的一件事。

「二分搜答案」是一個很常見的技巧：

題目問「最小的可行值是多少」，而你有辦法判斷「某個值可不可行」 ——那就可以對答案的範圍二分。

可行嗎？   ✗ ✗ ✗ ✗ ✓ ✓ ✓ ✓ ✓
答案:      1 2 3 4 5 6 7 8 9
                   ▲
             第一個可行的

只要那個「✗✗✗✓✓✓」的單調性成立，二分就用得上。 而被搜的東西根本不用存在記憶體裡。

完成的樣子

1#include <algorithm>2#include <iostream>3#include <vector>4using namespace std;5int main() {6    vector<int> v = {1, 3, 5, 7, 9};7    int idx = lower_bound(v.begin(), v.end(), 5) - v.begin();8    cout << idx << endl;9    return 0;10}

換你了

在 {1, 3, 3, 3, 5} 裡，用 upper_bound - lower_bound 數出 3 出現幾次。

再試著找一個不存在的數（例如 4），看 lower_bound 回什麼。

到編輯器做這一題：練習：用 upper_bound - lower_bound 數出 3 幾個

做一個

有序陣列 1 3 3 3 5 7。對 3、4、7 三個詢問，各印出它出現幾次。

🔴 不准用迴圈數。upper_bound 減 lower_bound 就是答案。 ⚠️ 4 不在裡面，而那兩個位置會指向同一個地方，所以答案是 0，不是錯誤。

到編輯器做這一題：做一個：這個數出現幾次（多筆詢問）

這一課你做了什麼

• 你用 lower_bound 在排好序的資料裡找到了位置
• 你知道找不到時它也會回一個位置，所以要自己檢查
• 你知道二分搜可以用在「答案的範圍」上

如果卡住了