d732. 二分搜尋法

思路

二分查找模板題。

二分搜尋法：常見坑點與避坑指南

1. 避免計算 mid 時溢位：當 left 和 right 都很大時，相加會超出 int 的範圍。
   • 寫法修正為 left + (right - left) / 2;
2. 死循環：在「二分答案」或尋找邊界時，如果區間縮小邏輯不對，left 和 right 會卡在同一個地方。
   • 如果你用 while(left < right)，你的更新必須確保區間在縮小，例如 left = mid + 1 或 right = mid。
   • 如果你用 while(left <= right)，兩邊都必須跳過 mid。
3. 邊界條件：到底最後要回傳 left 還是 right？
   • 自己拿比較小規模的測資去推，就知道最後的答案了，如果嫌麻煩，在程式碼中多設一個變數存著，只要 check(mid) 成功就紀錄。這樣就永遠存著最後一個合法的答案。
4. lower_bound 回傳的是第一個 $\geq{x}$ 的位置，如果陣列是 $[1,2,5]$，要找 3，它會回傳 5 的位置。
5. 在「二分答案」題目中，check 函數通常是 $O(n)$ 複雜度的。
   • 最常見錯誤：忘記處理單一元素就超過 limit 的情況。

程式碼

1. 二分查找

#include <iostream>
using namespace std;
const int MX = 100005;
int nums[MX];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) { // 輸入是嚴格遞增的，不需排序
        cin >> nums[i];
    }    
    bool found;
    int left, right, x;
    for(int i = 0; i < k; ++i) {
        cin >> x;
        found = false;
        left = 0, right = n - 1; // 閉區間
        while(left <= right) { 
            int mid = left + (right - left) / 2; // 避免溢位
            if(nums[mid] > x) { // 中間的數字比目標數字大，目標數字只有可能出現在左半邊，因此更新右邊界。
                right = mid - 1; // -1 確保依舊是閉區間
            }
            else if(nums[mid] == x) { // 找到目標數字，因為 nums[i] 是第 i + 1 個數字，輸出 mid + 1，
                cout << mid + 1 << "\n";
                found = true; // 標記為找到目標數字
                break;
            }
            else { // 中間的數字比目標數字小，目標數字只有可能出現在右半邊，更新左邊界。
                left = mid + 1;  // + 1 確保依舊是閉區間
            }
        }
        if(!found) cout << 0 << "\n";
    }

}

2. 庫函數

#include <iostream>
using namespace std;
const int MX = 100005;
int nums[MX];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
    }    
    for(int i = 0, x; i < k; ++i) {
        cin >> x;
        auto it = lower_bound(nums, nums + n, x); // 查找輸入的 n 個數字，第一個 >= x 的數字所在的位置
        if(it == nums + n || *it != x) { // 1. 如果沒找到，迭代器會在尾端。 2.找到的數字要確保 = x。
            cout << 0 << "\n";
        }
        else { // it 減去起點，得到位置，再 + 1
            cout << it - nums + 1 << "\n";
        }
    }

}

複雜度分析

• 時間複雜度：$O(n + k\log{n})$
• 空間複雜度：$O(n)$