基础课学习笔记（汇总）{:target=”_blank”}

bool check(int x) {/* ... */} // 检查x是否满足某种性质

int bsearch_1(int l, int r) {
    // 当 l == r 时，说明已经二分出答案
    while (l < r) {
        // A: 找中间值
        int mid = l + r >> 1;
        // B: 判断
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
int bsearch_2(int l, int r) {
    // 同理
    while (l < r) {
        // 注意边界问题
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}