第11章 二分查找

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

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