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

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
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;
}

下面我们来详细解释两个函数

bsearch_1: 用于区间 [l, mid] 和 [mid + 1, r] 的划分
示例：寻找数组中第一个大于等于某值的元素位置

int bsearch_1(int l, int r) {
    while (l < r) {                // 只要区间有多个点，就继续二分
        int mid = l + r >> 1;      // 计算中点，向下取整
        if (check(mid))            // 判断 mid 是否满足条件
            r = mid;               // 如果满足条件，右边界缩小到 mid
        else
            l = mid + 1;           // 如果不满足条件，左边界缩小到 mid + 1
    }
    return l;                      // 返回第一个满足条件的位置
}

执行过程

假设数组是 arr = {1, 3, 5, 7, 9}

初始：l = 0, r = 4
    mid = (0 + 4) / 2 = 2
    arr[2] = 5 < 6，check(2) = false
    更新：l = mid + 1 = 3

第一步：l = 3, r = 4
    mid = (3 + 4) / 2 = 3
    arr[3] = 7 >= 6，check(3) = true
    更新：r = mid = 3

停止：l = r = 3

结果：第一个大于等于 6 的元素位置是 3，即 arr[3] = 7。

bsearch_2 是另一种二分查找方法，适用于查找满足某种条件的最后一个位置。它的逻辑与 bsearch_1 相似，但区间的划分方式不同。

int bsearch_2(int l, int r) {
    while (l < r) {               // 循环条件：区间没有缩小到一个点
        int mid = l + r + 1 >> 1; // 计算中点（上取整），向右靠
        if (check(mid))           // 如果 mid 满足条件
            l = mid;              // 更新左边界为 mid
        else
            r = mid - 1;          // 如果 mid 不满足条件，更新右边界为 mid - 1
    }
    return l;                     // 返回最终位置
}

执行过程

初始：l = 0, r = 4
第一次计算：
    mid = (0 + 4 + 1) / 2 = 2
    check(2) 返回 true（arr[2] = 5 <= 6），更新 l = mid = 2
第二次计算：
    mid = (2 + 4 + 1) / 2 = 3
    check(3) 返回 false（arr[3] = 7 > 6），更新 r = mid - 1 = 2
停止条件：l == r == 2

结果：最后一个小于等于 6 的元素位置是 2。