二分查找

lowerBound(nums, target)

  • 核心要素

    1. 注意区间开闭，三种都可以
    2. 循环结束条件：当前区间内没有元素
    3. 下一次二分查找区间：不能再查找(区间不包含) $mid$，防止死循环
    4. 返回值：大于等于 $target$ 的第一个下标（注意循环不变量）

  • 有序数组中二分查找的四种类型（下面的转换仅适用于数组中都是整数）

    1. 第一个大于等于 $x$ 的下标： $lowerBound(nums, x)$
    2. 第一个大于 $x$ 的下标：可以转换为 第一个大于等于 $x+1$ 的下标，即 $lowerBound(nums,x+1)$
    3. 最后一个小于 $x$ 的下标：可以转换为 第一个大于等于 $x$ 的下标的左边位置, 即 $lowerBound(nums,x) - 1$;
    4. 最后一个小于等于 $x$ 的下标：可以转换为 第一个大于等于 $x+1$ 的下标的左边位置, 即 $lowerBound(nums,x+1) - 1$;

闭区间写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private int lowerBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1; // 闭区间 [left, right]
    while (left <= right) { // 区间不为空
        // 循环不变量：
        // nums[left-1] < target
        // nums[right+1] >= target
        
        // int mid = left + (right - left) / 2; 防止溢出
        int mid = left + right >> 1;
        if (nums[mid] < target) left = mid + 1; // 范围缩小到 [mid+1, right]
        else right = mid - 1; // 范围缩小到 [left, mid-1]
    }
    return left; // 或者 right+1
}

左闭右开区间写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 左闭右开区间写法
private int lowerBound(int[] nums, int target) {
    int left = 0, right = nums.length; // 左闭右开区间 [left, right)
    while (left < right) { // 区间不为空
        // 循环不变量：
        // nums[left-1] < target
        // nums[right] >= target
        
        // int mid = left + (right - left) / 2; 防止溢出
        int mid = left + right >> 1;
        if (nums[mid] < target) left = mid + 1; // 范围缩小到 [mid+1, right)
        else right = mid; // 范围缩小到 [left, mid)
    }
    return left; // 或者 right
}

开区间写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 开区间写法
private int lowerBound(int[] nums, int target) {
    int left = -1, right = nums.length; // 开区间 (left, right)
    while (left + 1 < right) { // 区间不为空
        // 循环不变量：
        // nums[left] < target
        // nums[right] >= target
        
        // int mid = left + (right - left) / 2; 防止溢出
        int mid = left + right >> 1;
        if (nums[mid] < target) left = mid; // 范围缩小到 (mid, right)
        else right = mid; // 范围缩小到 (left, mid)
    }
    return right; // 或者 left+1
}

左闭右闭二分

1
2
3
4
5
6
7
8
9
10
11
// 查找左边界 >= target
private int check(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        // int mid = left + (right - left) / 2; 防止溢出
        int mid = left + right >> 1;
        if (nums[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return right; // 或者 left
}
1
2
3
4
5
6
7
8
9
10
11
// 查找右边界 <= target
private int check(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        // int mid = left + (right - left) / 2; 防止溢出
        int mid = left + right + 1 >> 1;
        if (nums[mid] <= target) left = mid;
        else right = mid - 1;
    }
    return right; // 或者 left
}