二分算法总结

二分算法#

当 while (left <= right) 退出时，必然满足：

right + 1 == left

所以：

right 是最后一个 不满足 条件的下标
left 是第一个满足条件的下标

“找第一个 ≥ target” 的场景里，结果应返回 left（即成功区间的起点）。

名称	意义
`left`	当前区间的最小可能解
`right`	当前区间的最大可能解
退出条件	`left = right + 1`
若找第一个 ≥target	返回 `left`
若找最后一个 ≤target	返回 `right`

二分答案#

闭区间模板#

“花费一个 log 的时间，增加了一个条件。” —— 二分答案

「闭区间」写法的二分答案模板，用来寻找满足 check(x) == true 的最小整数 x。循环维护的是闭区间 [left, right]，使得：

check(left) 可能为 false；
check(right) 可能为 true；
一旦 check(mid) 成立，就缩小到左半区间，否则缩小到右半区间。

class Solution {
    // 计算满足 check(x) == true 的最小整数 x
    public int binarySearchMin(int[] nums) {
        int left = 0;    // 依题意选择最小可能的解
        int right = nums.length - 1; // 或者按题意设置最大可能的解
        while (left <= right) { // 闭区间不为空
            int mid = left + ((right - left) >> 1);
            if (check(mid, nums)) {
                right = mid - 1; // mid 已经满足，尝试压缩到更小的解
            } else {
                left = mid + 1;  // mid 不满足，丢弃左半边
            }
        }
        // 循环结束时 left 指向第一个满足 check 的位置
        return left;
    }

    // 根据题目的约束实现具体的校验逻辑
    private boolean check(int mid, int[] nums) {
        return false;
    }
}

参考灵茶山艾府题单