二分法

二分法是在有序区间中以 O(log n) 复杂度查找答案的方法。

不仅适用于：

• 完全有序数组
• 部分有序数组
• 单调函数
• 答案空间搜索

例如：

• LeetCode 704：二分查找
• LeetCode 34：查找元素第一个和最后一个位置
• LeetCode 33：搜索旋转排序数组
• LeetCode 153：寻找旋转数组最小值
• 各种「答案二分」

虽然二分法思想很简单，但是对于不同二分变形有很多细节问题。

二分法细节

二分法真正困难的不是思想，而是：

1. 区间定义
2. 循环条件
3. mid 取值方向
4. 区间更新方式
5. 死循环问题

所有二分模板，本质上都在维护：

“答案一定存在于当前区间中”

精确查找

使用的是左闭右闭区间，即

while(left<=right){}

每次更新中点时使用

mid = left + (right-left) / 2;
或者
mid = (left + right) >>> 1;
即向下取整

每次更新左右端点时使用

left = mid + 1;
或者
right = mid - 1;

适用场景： 数组无重复元素，或者你只需要随便找一个等于 target 的下标

public int binarySearchExact(int[] nums, int target) {
    if (nums == null || nums.length == 0) return -1;
    
    int left = 0;
    int right = nums.length - 1; // 1. 坑：左闭右闭区间，包括最后一个元素

    while (left <= right) { // 2. 坑：因为是双闭区间，left == right 时依然有效
        int mid = left + (right - left) / 2; // 3. 坑：防溢出的向下取整
        
        if (nums[mid] == target) {
            return mid; // 找到了直接返回
        } else if (nums[mid] < target) {
            left = mid + 1; // 目标在右边，排除 mid
        } else {
            right = mid - 1; // 目标在左边，排除 mid
        }
    }
    return -1; // 循环结束还没找到，说明不存在
}

第一个满足条件的位置/下界/上届

循环条件

while (left < right)

采用左闭右开区间

[left,right)

此时初始化为

left = 0;
right = length;

因为右开，所以不会越界

当left=right时，此时为空区间。

更新方式，因为不包含right位置的元素，所以

mid = right

下界（第一个等于 target 的位置）

适用场景： 数组中有重复元素，要求找第一个（最左边）等于 target 的下标

public int binarySearchLeftBoundary(int[] nums, int target) {
    if (nums == null || nums.length == 0) return -1;
    
    int left = 0;
    int right = nums.length - 1; 

    while (left < right) { // 1. 坑：锁定边界时，终止条件是 left == right，所以不带等号
        int mid = left + (right - left) / 2; // 2. 坑：配合下方的 right = mid，使用向下取整
        
        if (nums[mid] >= target) {
            // 当 mid 等于 target 时，它可能是第一个，也可能它右边还有别的
            // 所以我们不能用 mid - 1 把当前位置错过去，必须向左压缩区间
            right = mid; 
        } else {
            left = mid + 1; // 小于 target，mid 绝对不可能是答案
        }
    }
    
    // 3. 坑：循环结束时 left == right，必须进行后验（后验意味着检查这个边界值到底对不对）
    return nums[left] == target ? left : -1;
}

上界（查找最后一个等于target的位置）

public int binarySearchRightBoundary(int[] nums, int target) {
    if (nums == null || nums.length == 0) return -1;
    
    int left = 0;
    int right = nums.length - 1;

    while (left < right) { // 1. 坑：终止条件依然是 left == right
        // 2. 核心坑点：因为下方有 left = mid，这里必须使用【向上取整】（后面加 1）
        // 如果不加 1，当只剩 2 个元素时，mid 永远等于 left，若走入 left = mid 分支就会死循环
        int mid = left + (right - left + 1) / 2; 
        
        if (nums[mid] <= target) {
            // 当 mid 等于 target 时，它可能是最后一个，也可能它右边还有别的
            // 所以我们不能用 mid + 1 把当前位置错过去，必须向右压缩区间
            left = mid; 
        } else {
            right = mid - 1; // 大于 target，mid 绝对不可能是答案
        }
    }
    
    // 3. 坑：同样需要后验
    return nums[left] == target ? left : -1;
}

核心规律

1.闭区间

配套

right = n - 1;
while (left <= right)

因为

left == right 时仍然有元素

2.左闭右开

配套

right = n;
while (left < right)

因为

left == right 时为空区间

3.更新left=mid

mid必须向上取整

4.更新right=mid

mid必须向下取整

5.right = mid 和 right = mid - 1 的区别

取决于

mid 是否仍然可能是答案，是的话right = mid 否则 right = mid - 1

答案二分

答案二分的本质

不是在数组里二分元素。
而是在“答案空间”里二分最终结果。

很多题目根本没有“有序数组”，
但：

答案具有单调性

于是仍然可以二分。

例子：分割木头

有若干木头，
每段长度为 nums[i]

要求切成至少 k 段。

问：
每段最大能有多长？

如果：

x = 3 可行

那么：

x = 2
x = 1

一定也可行。

因为切得更短更容易。

于是：

true true true true false false

出现了。

完整代码

public int maxLength(int[] nums, int k) {

    int left = 1;
    int right = Arrays.stream(nums).max().getAsInt();

    while (left < right) {
        // 这里是找上界
        // 找最大可行值
        // 所以这里必须上取整
        int mid = left + (right - left + 1) / 2;

        if (check(nums, k, mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    return left;
}

private boolean check(int[] nums, int k, int len) {

    int count = 0;

    for (int x : nums) {
        count += x / len;
    }

    return count >= k;
}

答案二分的本质

其实是：

把“求最优解”

转化为：

“判定某个答案是否可行”

最大值最小化

经典：

给数组分组，
使每组和的最大值最小

例如：

LeetCode 410

二分：

答案 = 最大组和

check：

能否在 <= k 组内完成
最小值最大化

经典：

奶牛之间最小距离最大

例如：

洛谷 aggressive cows
LeetCode 1552

二分：

答案 = 最小间距

check：

能否放下 k 头牛

什么时候能想到答案二分

看到：

1. 求最大最小值

例如：

最大化最小值
最小化最大值

2. 答案范围巨大

例如：

1 ~ 10^18

暴力枚举不可能。

3. 存在明显单调性

例如：

mid 越大越难满足

或者：

mid 越小越容易满足

答案二分真正的数学本质

本质上是在二分：

单调布尔函数

答案二分模板

int left = 最小可能答案;
int right = 最大可能答案;

while (left < right) {

    int mid = left + (right - left + 1) / 2;

    if (check(mid)) {
        left = mid;
    } else {
        right = mid - 1;
    }
}

return left;