二分查找

发表于 | 分类于 ， | | 阅读次数:

二分查找

参考网址1

参考网址2

适合场景：

  • 寻找一个数
  • 寻找左侧边界
  • 寻找右侧边界

最大的一个前提是：需要在单调区间内

1. 框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(int[] nums, int target){
    int left = 0, right = ...;
    while(...){
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){
            ...
        }else if(nums[mid] > target){
            ...
        }else if(nums[mid] < target){
            ...
        }
    }
    return ...;
}

2. 寻找一个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) { // 注意
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length; // 注意

    while(left < right) { // 注意
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid; // 注意
        }
    return -1;
}

while(left <= right) 这里是 <= 是因为要把区间里所有的数据都判断一遍，如果是 while(left < right) 那么 left = right 的这个下标对应的数据就没有进行判断，可以修改return来达到最终目标 while(left < right){...} return nums[left] == target ? left : -1;

  1. 此算法有什么缺陷？
    答：至此，你应该已经掌握了该算法的所有细节，以及这样处理的原因。但是，这个算法存在局限性。
    比如说给你有序数组 nums = [1,2,2,2,3]，target = 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。
    这样的需求很常见。你也许会说，找到一个 target 索引，然后向左或向右线性搜索不行吗？可以，但是不好，因为这样难以保证二分查找对数级的复杂度了。

3. 寻找左侧边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
①
int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}
②
int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length - 1; // 注意

    while (left <= right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; // 注意
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

int right = nums.length 表示 [left, right) 范围内的数据都要考虑，而 right 对应的数据不做考虑，所以当 nums[mid] > target 时， right = mid 即可。而当 nums[mid] == target 时，因为目标是拿到做边界，所以需要让 right = mid 来压缩区间范围，向左靠拢

更推荐第一种，从左侧边界这个点考虑，需要求出来的是一个index，小于这个index的所有数据都是小于target的，而不去关心右侧边界具体是什么，那么搜索区间保证是 [left, right) 即可

4. 寻找右侧边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
①
int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; 
        }
    }
    return left - 1; // 注意
}

②
int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

nums[mid] == target 时压缩右侧区间，所以让 left = mid + 1。最后返回 left - 1 和 right - 1是一样的，因为 while 退出的时候，left 和 right 相等，-1 可以这样想，如果 nums[mid] == target 时，left = mid + 1 也就是 mid = left - 1，最后返回的时候，left 对应的值不是等于 target 的下标，而 -1 后的 mid 有可能符合结果。

5. 总结

在寻找左侧或右侧边界的时候，设想 nums=[1, 2, 2, 2, 3]，需要target=2的左侧和右侧，保证 [left, right) 左闭右开的搜索区间