這是 Aloe【菜鳥勇闖演算法】的第一篇文章。這篇文章筆者與讀者一起手撕「二分搜尋法」。我們從生活中的真實例子出發，引出二分搜尋法的優點。

前言：關於「二分搜尋法」的直覺

找書

小明和 Siao 前往了圖書館。圖書館一共有 12345 本書，在同學們的維護下，書的編號是從小到大排列的，但是有些書本丟失了，他們想看看編號為 8000 的書本到底是否還在書架上。

  • 小明看著長長的書架一眼望不到頭，只好隨意翻弄書本。

  • Siao 先是走到了書架的正中間，看了一下這本書的編號是 6200，心想：「6200 比我要找的 8000 小，說明左邊這一半書架（1~6200）全是垃圾，看都不用看！」於是直接走到了右半邊区域的中間；發現書的編號是 9500，於是又向左走了一半 …… Siao 很快就發現編號 8000 的書本不在。

像 Siao 這樣每次都捨棄一半的搜尋空間（書本），在搜尋空間中不斷「二分」的演算法叫做「二分搜尋法」。

思考： 如果書本的編號不是從小到大的有序排列，我們還能像這樣二分搜尋了嗎？

思考： 如果要找編號為 8001 的書本，並且這套書有很多卷（8001-A、8001-B、…）。小明和 Siao 要分別找 8001-A（第一卷） 和 8001-?（最後一卷），那麼找到某一卷 8001 之後就停手，可以嗎？還需要怎麼找？如何計算 8001 總共有多少卷？

猜數字遊戲

小明和 Siao 在玩一個猜數字遊戲，遊戲規則是在 1-100 之內喊一個整數，裁判會告訴玩家猜大了還是猜小了。Siao 心生一計，邪魅一笑；而小明卻不知所措。據說當時的遊戲情景是這樣的：

  • 小明：
    • 90！裁判：猜大了！
    • 20！裁判：猜小了！
    • 25！裁判：猜小了！
    • 40！裁判：猜小了！
    • 45, 55, 65, …
    • 好難，不要玩了…
  • Siao：
    • 先猜 (1+100) / 2 = 50
    • 50！裁判：猜小了！ -> 排除 1-50，鎖定範圍 [51, 100]，下一次猜 (51+100) / 2 = 75
    • 75！裁判：猜小了！ -> 排除 51-75，鎖定範圍 [76, 100]，下一次猜 (76+100) / 2 = 88
    • 88！裁判：猜大了！ -> 排除 88-100，鎖定範圍 [76, 87]，下一次猜 (76+87) / 2 = 81
    • 81！裁判：猜大了！ -> 排除 81-87，鎖定範圍 [76, 80]，下一次猜 (76+80) / 2 = 78
    • 78！裁判：猜小了！ -> 排除 76-78，鎖定範圍 [79, 80]，下一次猜 (79+80) / 2 = 79
    • 79！裁判：猜小了！ -> 排除 79，鎖定數字 80，下一次猜 80
    • 80！裁判：猜中！

Siao 只用了 7 步就猜中了數字，而小明卻仍然在亂猜。事實上觀察 Siao 喊出的數字可以發現，Siao 每次都是喊出當前已知的最小和最大的數字的平均值。

像 Siao 這樣每次都捨棄一半的答案空間（要猜的數字），這種在答案空間不斷「二分搜尋」的演算法叫做「二分答案」。

用圖片表示使用二分搜尋法「找書」的過程

武器庫：一個通用的模板

必須承認的是，寫二分搜索的演算法時，最令人頭疼的不是程式碼的邏輯，而是邊界條件：

  • 要寫 while (left < right) 還是 while (left <= right)？

  • 要寫 mid + 1 還是 mid - 1？

這裡給出一個筆者在用的模板，筆者認為這個模板是比較符合正常的思維的，寫起來不會感到特別「反直覺」。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int binary_search(const vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    int ans = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] < target) {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid - 1;
        }
        else {
            ans = mid;

            // break; 
            // right = mid - 1;
            // left = mid + 1;
        }
    }

    return ans;
}

程式碼解讀：

  1. 我們預設 nums 陣列是「不降」的（也就是從小到大排列的）。

    • 如果得到了從大到小排列的陣列，可以呼叫 std::ranges::reverse() 或 std::reverse() 函式。
    • 或者把 > target 和 < target 的邊界調整互換。

    提示： 若需呼叫 std::ranges::reverse() 或 std::reverse() 函式，需包含 algorithm 標頭檔。其中 std::ranges::reverse() 需要 C++ 20。

  2. 第 6 列，這樣寫等價於 mid = (left + right) / 2，但是我們這種寫法能防止潛在的 left + right 加法溢出。

  3. 第 9 列，若滿足 nums[mid] < target，則說明我們找的數字小了。

    • 我們要找的數字的位置在 mid 右側，並且 mid 這個位置本身的數字也不是我們要找的。
    • 所以把 left 移至 mid + 1 的位置。

  4. 第 12 列，同第九列。

  5. 第 15 列，我們終於找到了一個數字，位置就是 mid。我們先保存起來。

    隨後我們面臨三個抉擇：

    • 如果我們只要確認「是否存在」，或者隨便找一個位置就好了，就直接跳出迴圈，傳回這個 ans。
    • 如果我們要找「左側邊界」，則把這個結果視為「找的數字大了」：right = mid - 1;
      • 這解答了思考題2：如何尋找 8001-A。
    • 如果我們要找「右側邊界」，則把這個結果視為「找的數字小了」：left = mid + 1;
      • 這解答了思考題2：如何尋找 8001-?。

  6. 第 23 列，我們可能傳回：

    • 一個非負整數。這代表我們在 nums 中搜尋到到的某一個值為 target 的位置。
    • 或者 -1。這代表整個迴圈流程中從未滿足 nums[mid] == target）條件，即在 nums 中未能找到 target。
      • 這也是找書問題中，未找到 8000 號書對應的情況。

  7. 時間複雜度是 O(log n)。

實戰演練：從卡殼到破局

題目一：A-B 數對，洛谷 P1102

A. 題目簡述：給定正整數陣列和正整數 C，從陣列中找出滿足 A - B = C 的數對的個數。

B. 第一直覺與暴力解法：

  • 寫一個兩層迴圈，暴力枚舉 A 和 B，時間複雜度 O(n2)： 
    1
    2
    3
    4
    5
    for (int a = 0; a < n; a++) {
        for (int b = a + 1; b < n; b++) {
            if (a - b == c) ans++;
        }
    }

    警告： 這道題 1 ≤ N ≤ 2 × 105，時間限制 1.00s。如果是 O(n2) 的時間複雜度，會有 1010 數量級次數的運算，會 TLE。

C. 思路卡殼：

  • 靈感：由於題目並未規定從陣列中取數字的先後次序，則可以「跳著選擇」。因此考慮將陣列排序後採用「二分搜尋法」找出符合要求的 A 和 B。

  • 困惑：但是由於需要搜尋兩個變數 A 和 B，與我們剛剛提到的「找書」問題有較大差異。開始懷疑「二分搜尋法」的正確性。

D. 破局點：

  • 轉換視角：考慮利用等式變換，將 A - B = C 問題變換為 A = B + C 問題。

  • 變數固定：考慮消去 B 變數，想到可以寫一個迴圈，每次選擇一個固定的 B，這樣就只剩 A 這一個變數，而要搜尋的數字 target 就等於 B + C。

  • 可行性驗證：外層迴圈，時間複雜度為 O(n)；內層二分搜尋，時間複雜度為 O(log n)。總時間複雜度為 O(nlog n)，運算次數的數量級為 106，可以在 1.00s 時間內運行完畢。

  • 計算滿足要求數對的個數：這是思考題 2 的最後一個小問題。考慮計算出 target 的左邊界 ans_left 與右邊界 ans_right，之後算減法再 +1，即 Counttarget = ansright − ansleft + 1。

E. 程式碼實現：

  • 根據以上的思考，我們就可以寫出這樣的程式碼： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    int n, c, ans = 0;
    cin >> n >> c;

    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    // 讀入資料後，第一件事：排序！
    // 二分搜尋的前提是單調性！
    ranges::sort(nums);

    for (int b = 0; b < n; b++) {
        // 由於 C >= 1，因此 target > nums[b]，所以直接從 b + 1 的位置開始搜尋。
        int left = b + 1, right = n - 1;
        int target = nums[b] + c;
        int ans_left = -1, ans_right = -1;

        // 搜尋左邊界
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            }
            else if (nums[mid] > target) {
                right = mid - 1;
            }
            else {
                ans_left = mid;
                right = mid - 1;
            }
        }

        left = b + 1, right = n - 1;

        // 搜尋右邊界
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            }
            else if (nums[mid] > target) {
                right = mid - 1;
            }
            else {
                ans_right = mid;
                left = mid + 1;
            }
        }

        // 如果 ans_left（或 ans_right）等於 -1，則沒有搜尋到 target，ans 不變。
        if (ans_left != -1) {
            ans += ans_right - ans_left + 1;
        }
    }

    cout << ans << endl;

F. 程式碼壞味道與最佳化：

我們剛剛寫出的程式碼雖然可以正確地解決問題，可是卻有兩個幾乎一模一樣的 while 迴圈（計算左右邊界），這在工程中被稱作「程式碼壞味道」。

那麼，是否有一種方法可以省去這兩個幾乎完全一樣的迴圈呢？

使用 std::lower_bound 與 std::upper_bound 函式

提示： 若需呼叫 std::lower_bound 或 std::upper_bound 函式，需包含 algorithm 標頭檔。

  1. 呼叫： std::lower_bound(first, last, target);

    一般地，對整個 STL 容器搜尋（如 std::vector<int> nums）：

    • first = nums.begin()，last = nums.end()。

  2. 功能簡述： std::lower_bound 與 std::upper_bound 是 STL 提供的「二分搜尋法」函式，對於一個「升序」的陣列：

    • lower_bound：回傳在 [first, last) 中，第一個滿足 elem >= target 的位置（疊代器），若未能找到回傳 last。
    • upper_bound：回傳在 [first, last) 中，第一個滿足 elem > target 的位置（疊代器），若未能找到回傳 last。

    對於隨機存取容器，時間複雜度為 O(log n)。

  3. 常用用法：

    1. 尋找 target 的左右邊界： 

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      auto it_low = std::lower_bound(first, last, target);
      auto it_up  = std::upper_bound(first, last, target);

      if (*it_low == target) {
          // 情形 1：it_low 是陣列中指向第一個 target 的疊代器（左側邊界）。
          // 轉換為索引，則 index_left = it_low - first;
      }
      else if (it_low != last) {
          // 情形 2：陣列中沒有等於 target 的元素，it_low 是第一個大於 target 的疊代器。
          // 此時 it_low == it_up。
      }
      else {
          // 情形 3：target 比陣列中所有元素都大。
          // 此時 it_low == it_up, it_low == last。
      }

      if (*(it_up - 1) == target) {
          // 情形 1：it_up 是陣列中指向第一個大於 target 的疊代器（右側邊界 + 1）
          // 轉換為索引，則 index_right = it_up - first - 1;
      }
      else if (it_up != last) {
          // 情形 2：陣列中沒有等於 target 的元素，it_up 是第一個大於 target 的疊代器。
          // 此時 it_up == it_low。
      }
      else {
          // 情形 3：target 比陣列中所有元素都大。
          // 此時 it_up == it_low, it_up == last。
      }

    2. 尋找 target 的個數： 結論：Counttarget = itup − itlow。

      思考： 為什麼不是 Counttarget = itup − itlow + 1？

      思考： 對於剛剛提到的情形 2（沒有相等）與情形 3（大於所有元素），使用此結論之前是否需要經過 if 條件判斷？

  4. std::binary_search 簡述：

    • 呼叫：std::binary_search(first, last, target)，回傳一個布林值。
      • true：利用二分搜尋找到了一個 target。
      • false：未能找到一個 target。

    僅適用於確認「是否存在」，或者隨便找一個位置的情形。

  5. 最佳化程式碼：

    現在，我們已經懂得 std::lower_bound 或 std::upper_bound 函式的基本用法，現在讓我們使用這兩個函式來重構題目一的程式碼。

    題目一的程式碼異味，來源於 target 個數的計算，為此我們引入了兩個幾乎一模一樣的 while 迴圈。利用剛剛學習到的結論重寫之：

    1
    2
    3
    4
    5
    6
    for (int b = 0; b < n; b++) {
        auto it_low = lower_bound(nums.begin(), nums.end(), nums[b] + c);
        auto it_up  = upper_bound(nums.begin(), nums.end(), nums[b] + c);

        ans += it_up - it_low;
    }

    瞬間變得清爽整潔，可讀性大大增加。

G. 總結：

這道題我們首先利用等式的性質，變換為 A = B + C 的問題，同時利用一層迴圈固定 B 變數，這樣就是一個標準的「單變數」二分搜尋。

使用二分搜尋找出左右邊界。個數的計算公式為 Counttarget = ansright − ansleft + 1。

為了簡化二分搜尋的程式碼的編寫，我們學會了如何使用 std::lower_bound 與 std::upper_bound 函式，並得出新的計算公式為 Counttarget = itup − itlow。

思考題解答：

  • 由於 std::upper_bound 找的是「大於」的位置。相當於自動幫我們 +1 了，因此不需要另外 +1。

  • 如果 std::lower_bound 與 std::upper_bound 沒有找到 target，則 it_up == it_low，相減等於 0，符合計算直覺，不需要額外的 if 判斷。

題目二：木材加工，洛谷 P2440

A. 題目簡述：給定正整數陣列 L 和正整數 k，分別代表「原木數量」與「最少段數」。求滿足「最少段數」的情況下，每段原木可以切的最長的長度是多少。

B. 第一直覺與暴力解法：

  • 寫一個迴圈，從 1 到 sum / k，暴力枚舉可能的長度。在仍能至少切出 k 段的前提下，找到最大的 l，時間複雜度 O(n2)： 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    for (int l = 1; l <= sum / k; l++) {
        int parts = 0, ans = 0;

        for (auto i : L) {
            parts += i / l;
        }

        if (parts >= k) {
            ans = l;
        }
    }

    無法通過所有測試用例，因此我們需要一種更快速的解法。

C. 破局點：

  • 目前的困境：我們從 1 嘗試到 sum / k，這太慢了，或者說不能很快地排除掉不合理的答案空間。

  • 靈感：為了快速排除掉答案空間，由「猜數字」遊戲的啟發，我們可以嘗試「二分答案」的做法。

  • check 函式設計：與「二分搜尋」不同，mid 與 target 並不是簡單的大小關係；在「二分答案」演算法中，mid 與我們要搜尋的答案可能有更複雜的關係。這個「複雜的關係」我們一般叫做「check 函式」，check 函式對給定的 mid 計算，使用回傳值與 target 相比較。

    • 在這道題中，我們把「切割的長度」二分，則 mid 就是本輪二分的切割長度。因此我們計算使用 mid 長度切割原木，可以切割出的段數 parts，將這個 parts 與題目中的「最少段數」比較：

      • parts > k：也就是 mid 太小，切的太碎，是一個合法的答案。但下一輪可以嘗試讓 mid 更大一些：left = mid + 1。

        注意： 雖然 parts > k，但是仍然滿足了「至少 k 段」的要求，因此可以暫存當前的結果 mid：ans = mid。

      • parts < k：也就是 mid 太大，切的太大塊，沒能滿足題目中「至少 k 段的要求」。下一輪讓 mid 更小一些：right = mid - 1。

      • parts == k：也就是正好可以切成 k 段，是一個合法的答案。暫存當前的結果 mid：ans = mid。但是仍需考慮繼續增大 mid 的大小：left = mid + 1。

        提示： 假設 L = [5, 6, 7]，k = 3，mid = 4。當前 parts = 5/4 + 6/4 + 7/4 = 3，已經滿足題目 k 的要求。考慮增大 mid = 5：則 parts = 5/5 + 6/5 + 7/5 = 3，仍然符合 k 的要求，但顯然現在的 mid 更大。所以「仍需考慮繼續增大 mid 的大小」的做法是合理且必要的。

    • check 函式走訪了整個 L 陣列，因此時間複雜度是 O(n)。

  • 可行性驗證：外層二分搜尋，時間複雜度為 O(log n)；內層檢查迴圈時間複雜度為 O(n)。總時間複雜度為 O(nlog n)。最差情況下，運算的數量級為 106，可以在 1.00s 時間內運行完畢。

D. 程式碼實現：

  • 根據我們以上的分析，我們可以寫出這樣的程式碼： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    int n, k, sum = 0, ans = 0;
    cin >> n >> k;

    vector<int> L(n);
    for (int i = 0; i < n; i++) {
        cin >> L[i];
        sum += L[i];
    }

    int left = 1, right = sum / k;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int parts = 0;
        for (auto i : L) parts += i / mid;

        if (parts > k) {
            left = mid + 1;
            ans = mid;
        }
        else if (parts < k) {
            right = mid - 1;
        }
        else {
            ans = mid;
            left = mid + 1;
        }
    }

    cout << ans << endl;

E. 總結：

這道題我們從「暴力枚舉切割長度」開始，將思路轉向了「使用二分答案搜尋長度」。

我們根據題目的實際情況思考並設計了 check 函式，並且考慮到了 parts > k 可能就是一個可行解、parts == k 未必就是最終解的情況。避免潛在的漏解或錯解的情形。

附錄

程式碼框架

在有關於演算法題目的程式碼中，筆者通常會使用這樣的程式碼框架： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 俗稱「萬用標頭檔」，在「多數情況下」可以只包含這一個標頭檔，就不必寫出其他內建函式屬於哪個標頭檔了。
// 「多數情況」：不要過度依賴萬用標頭檔，這個檔案並不在 C++ 的官方規範中，屬於 GCC 的特性，在 MSVC 等編譯器中就不適用了。
// 內建函式與類別所屬的標頭檔是必須記憶的，而不是可選項！
#include <bits/stdc++.h>

using namespace std;

#define MULTI_TEST 0
#define int long long

void solve() {
    // TODO: 部落格展示的程式碼方塊，通常會從這裡開始寫。
}

// int 已經被替換為 long long，而 long long 不能作為 main 函式的返回型別。
// 而 signed 與 signed int, int 是相同的型別，所以我們藉助這個特性，使用 signed 替換 int。
signed main() {
    // 取消 stdio 與 iostream 的同步，這會顯著增加 cin/cout 的效能。
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 用於控制是是單/多測試用例，如果是多測試用例，需要將上方的 MULTI_TEST 巨集的值更改為 1，反之亦然。
    int t = 1;
    if (MULTI_TEST) {
        cin >> t;
    }

    // 執行 t 次 solve 函式，單/多測試用例通用。
    while (t--) {
        solve();
    }

    return 0;
}

寫在最後

回頭看這兩道題，其實代碼都不長，但難點在於如何從 O(N)的暴力直覺，跨越到O(log N) 的二分思維。

這也是我寫這個系列的初衷：演算法最難的往往不是寫出代碼的那一刻，而是「想到可以這樣做」的那一瞬間。從 P1102 的 TLE 到 P2440 的二分答案，我們學習的不僅是 left 和 right 的移動，更是一種「透過排除法逼近真相」的思維方式。

演算法這條路很長，我們切題的時候或許可以慢一點，但像二分搜尋一樣，只要方向對了，每一步都在縮小與答案的距離。這是 Aloe 演算法之路的第一站，我們下一篇文章見。