整数二分

原理

见《进阶指南》第26页。

代码

while (l < r) {
    int mid = l + r + 1 >> 1;
    if (check(mid) == true) // 满足条件 1
        l = mid;
    else
        r = mid - 1;
}

while (l < r) {
    int mid = l + r >> 1;
    if (check(mid) == true) // 满足条件 2
        r = mid;
    else
        l = mid + 1;
}