2.2 KiB

Raw Permalink Blame History

二分查找

二分的本质并非“单调性”，而是“边界”，只要找到某种性质，使得整个区间一分为二，那么就可以用二分把边界点二分出来。

算法模板

模板 1

boolean check(int x) {
}

int search(int left, int right) {
    while (left < right) {
        int mid = (left + right) >> 1;
        if (check(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

模板 2

boolean check(int x) {
}

int search(int left, int right) {
    while (left < right) {
        int mid = (left + right + 1) >> 1;
        if (check(mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

做二分题目时，可以按照以下套路：

写出循环条件 left < right；
循环体内，不妨先写 mid = \lfloor \frac{left + right}{2} \rfloor；
根据具体题目，实现 check() 函数（有时很简单的逻辑，可以不定义 check），想一下究竟要用 right = mid（模板 1）还是 left = mid（模板 2）； - 如果 right = mid，那么写出 else 语句 left = mid + 1，并且不需要更改 mid 的计算，即保持 mid = \lfloor \frac{left + right}{2} \rfloor； - 如果 left = mid，那么写出 else 语句 right = mid - 1，并且在 mid 计算时补充 +1，即 mid = \lfloor \frac{left + right + 1}{2} \rfloor；
循环结束时，left 与 right 相等。

注意，这两个模板的优点是始终保持答案位于二分区间内，二分结束条件对应的值恰好在答案所处的位置。对于可能无解的情况，只要判断二分结束后的 left 或者 right 是否满足题意即可。

例题