二分搜

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

你會學到三件事

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

開始之前

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

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

一、lower_bound

vector<int> v = {1, 3, 5, 7, 9};
int idx = lower_bound(v.begin(), v.end(), 5) - v.begin();
cout << 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 不在裡面。

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

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

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

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

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

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

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

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

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

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

完成的樣子

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

換你了

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

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

這一課你做了什麼

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

如果卡住了