二分模板

#include <bits/stdc++.h>
using namespace std;

// 二分查找：找 >= target 的最小值
int lowerBound(int a[], int n, int target) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 二分查找：找 > target 的最小值
int upperBound(int a[], int n, int target) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 二分答案模板
bool check(int mid) { return true; /* 判断mid是否满足条件 */ }
int binaryAnswer(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

int main() {
    int a[] = {1, 3, 3, 5, 7, 9};
    cout << lowerBound(a, 6, 3) << endl;  // 1
    cout << upperBound(a, 6, 3) << endl;  // 3
    return 0;
}

📖 要点说明

• lo + (hi-lo)/2 防溢出，比 (lo+hi)/2 安全
• lower_bound: 第一个 >= target，upper_bound: 第一个 > target
• 二分答案：对结果范围二分，用 check 验证

⚠️ 常见错误

• 死循环：lo=mid 忘 +1 或 hi=mid 忘不 +1
• 区间开闭不统一
• 二分答案时 check 函数逻辑写反