書接上回:
【演算法新手村】[初階]筆記02 - 初識二分之常見問題

二分答案會有點困難，可以多思考，只要能掌握那怕毛皮，那你也是終於"略懂"二分了
新手可以直接跳到下面看練習題

二分答案

有時候，題目並不是給你一個排好序的陣列要你找東西，而是問你：滿足某個條件的最小值是多少？ 或是 在有限限制下，最大的可能效率是多少？

這時候，我們可以不去直接算答案，而是猜一個答案，然後檢查這個答案行不行。

什麼時候可以用？

並不是所有問題都能二分搜答案。它必須具備 單調性 (Monotonicity)。
舉抽象的例子來說
如果答案 x是可行的，那比 x更小的（或更大的）答案也一定可行。
例：如果你能扛起 20 公斤的重物，那你一定能扛起 10 公斤的。(簡單題大多類似這種)

經典範例：伐木工問題

題目描述：
你需要 M公尺的木材。你有一排樹，高度分別為 trees[]。你設定一個鋸片高度 H，所有比 H高的樹木都會被鋸掉剩下的部分歸你。請問：鋸片高度最大可以設定為多少，才能讓你拿到至少 H公尺的木材？

邏輯：

• 如果鋸片設在 100 公尺可以拿到足夠木材，那設在 80 公尺一定也可以（但高度變低了，不是我們要的最大高度）
• 具備單調性，所以我們可以對高度H二分搜尋。

程式碼實作 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 如果鋸片高度設為 H，拿到的木材是否 >= M?
bool check(long long H, const vector<int>& trees, int M) {
    long long total = 0;
    for (int tree_h : trees) {
        if (tree_h > H) {
            total += (tree_h - H);
        }
    }
    return total >= M;
}

int main() {
    int N = 4; // 4 棵樹
    int M = 7; // 需要 7 公尺
    vector<int> trees = {20, 15, 10, 17};

    long long low = 0, high = 20; // 高度範圍在 0 到最最高的那棵樹
    long long ans = 0;

    while (low <= high) {
        long long mid = low + (high - low) / 2;

        if (check(mid, trees, M)) {
            ans = mid;      // 目前高度可以，記錄下來
            low = mid + 1;  // 試試看能不能再設高一點 (拿少一點木材)
        } else {
            high = mid - 1; // 太高了，拿到的木材不夠，鋸片要調低
        }
    }

    cout << "Best Height: " << ans << endl; // 輸出 15
    return 0;
}

思考過程

1. 確定範圍：答案最小可能是多少 (low)？最大可能是多少 (high)？
2. 寫出檢查函式 check(mid)：這通常是一個簡單的 bool 函式。給它一個數值 mid，它會告訴你「這個答案是否符合題目規定」。
3. 開始二分搜：
   • 如果 mid 可以，我們就試試看能不能更好（往更優的方向找）。
   • 如果 mid 不行，我們就得退而求其次（往寬鬆的方向找）。

二分搜尋法不僅僅是在陣列裡找數字。它更像是一種效率極高的猜答案策略。只要滿足單調性，你就能把一個複雜的優化問題，簡化成一個簡單的是非題。

練習區

這邊附上一些大家可以練習的題目，如果哪邊不會寫可以再多思考，當然也可以直接留言，我只要有看到都會回答喔。
如果我看到適合放到這邊的題目會繼續放到這邊，這些題目懂過個學校考試應該沒什麼問題...吧?

vector陣列長度可以用 .size() 獲取

筆記01 區

1. Binary Search - LeetCode

筆記02 區

1. Search Insert Position - LeetCode

LeetCode 35. Search Insert Position 詳解

筆記03 區

1. Find Peak Element - LeetCode
2. Sqrt(x) - LeetCode

更多題目可以在各大平台上找，現在資源很多應該不是甚麼問題，二分的基礎到這邊就結束了。
關於二分，雖然概念不難，但真的要多加練習才能掌握，如果二分答案真的不會寫也不用太氣餒，大概率是我講的不夠清楚owo，哪裡不懂可以留言，我會盡我所能解答，當然如果我有甚麼偏誤也歡迎指出，這些例題我也會寫題解(筆記01的題太簡單了，略)，下一篇見~。