二分模板

二分模板一共有两个，分别适用于不同情况

算法思路：假设目标值在闭区间 $[L,R]$ 中，每次将区间长度缩小一半，当 $L = R$ 时，我们就找到了目标值

版本 1

当区间 $[L,R]$ 的更新操作是 $r = mid; l = mid + 1$

这种方式使得中点 $mid$ 属于左半区间，则左半区间是 $[L, mid]$，右半区间是 $[mid + 1, R]$

int binary(int l, int r) {
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (check(mid))
            r = mid; // 左
        else
            l = mid + 1; // 右
    }
    return l;
}

例题：LeetCode 275. H-Index II

版本 2

当区间 $[L,R]$ 的更新操作是 $r = mid - 1; l = mid$ 时

这种方式使得中点 $mid$ 属于右半区间，则左半区间是 $[L,mid - 1]$，右半区间是 $[mid,R]$

int binary(int l, int r) {
    while (l < r) {
        int mid = 1 + l + ((r - l) >> 1);
        if (check())
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

例题：LeetCode 69. Sqrt(x)