二分查找与二分答案CSP-J

💡 核心思想

二分查找是在有序序列中快速定位目标元素的算法，时间复杂度为 O(log n)。二分答案是更高级的应用：当问题的答案具有单调性时（即"如果 x 可行，则所有小于 x 的也一定可行"），可以通过二分来寻找最优解，将判定问题转化为验证问题。

🎯 直觉理解

想象你在词典里查一个单词。你不会从第一页开始翻，而是先翻到中间，看目标单词在左半边还是右半边，然后继续折半——这就是二分查找。二分答案则像"猜数字游戏"：我猜 50，你告诉我是大了还是小了，我再猜 25 或 75，每次都能排除一半的可能性。

📝 算法流程

1. 确定搜索区间 [l, r]，确保答案一定在区间内
2. 计算中点 mid = (l + r) / 2（或根据情况调整）
3. 比较 mid 与目标值：如果 mid 太小，则答案在右半区间 [mid+1, r]；如果 mid 太大，则答案在左半区间 [l, mid-1]
4. 重复步骤 2-3 直到 l > r（查找）或 l == r（二分答案）
5. 二分答案需额外编写 `check(x)` 函数验证可行性

$$T(n) = O(log n) \text{（每次排除一半元素）}$$

$$\text{二分答案框架：while }(l < r)\text{ 取 }mid\text{，若 }check(mid)\text{ 成立则 }r = mid\text{，否则 }l = mid + 1$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

// 1. 标准二分查找：在有序数组中找 target
int binarySearch(vector& a, int target) {
    int l = 0, r = a.size() - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (a[mid] == target) return mid;
        else if (a[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1; // 未找到
}

// 2. lower_bound：第一个 >= target 的位置
int lowerBound(vector& a, int target) {
    int l = 0, r = a.size(); // 注意 r = size()
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[mid] < target) l = mid + 1;
        else r = mid;
    }
    return l;
}

// 3. 二分答案示例：找出最小的 x 使得 f(x) >= target
bool check(long long x) {
    // 验证 x 是否可行
    return x * x >= 100; // 示例：找平方 >= 100 的最小数
}
long long binaryAnswer() {
    long long l = 0, r = 1e9;
    while (l < r) {
        long long mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l; // l == r 时就是答案
}

int main() {
    vector a = {1, 3, 5, 7, 9, 11, 13};
    cout << binarySearch(a, 7) << endl; // 3
    cout << lowerBound(a, 6) << endl;   // 3 (a[3]=7 是第一个 >=6 的)
    cout << binaryAnswer() << endl;     // 10
    return 0;
}

⚠️ 常见坑点

📚 相关题目