【每日算法Day 38】二分查找1

关于二分查找，Knuth大佬说过：

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky...

所谓思路很简单，细节是魔鬼，需要小心避免边界条件出错，弄清楚到底要给 mid 加一还是减一，while 里到底用 <= 还是 <。

# LeetCode 278. 第一个错误的版本 (opens new window)

# 题目描述

Git bisect用过吗？本题就和与之相吻合，假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

# 示例

给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。

1
2
3
4
5
6
7

# 解题思路

当调用isBadVersion发现mid是错误的版本时，搜索区间变为[left,mid]则right=mid; 当调用isBadVersion发现mid是正确的版本时，搜索区间变为(mid,right]则left=mid+1; 循环终止时，left=mid+1=right，这是left是第一个错误的版本。

public int firstBadVersion(int n) {
    //都能取到，闭区间搜索
    int left=1,right=n;
    while(left<right){
        int mid=left+((right-left)>>1);
        if(isBadVersion(mid)){
            //第一个错误的版本在[left,mid]中
            right=mid;
        }else{
            //第一个错误的版本在[mid+1,right]中
            left=mid+1;
        }
    }
    //最终left=right，只有一个位置，则必然是第一个错误的版本
    return left;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# LeetCode 35. 搜索插入位置 (opens new window)

# 题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

# 示例

示例 1:
输入: [1,3,5,6], 5
输出: 2

示例 2:
输入: [1,3,5,6], 2
输出: 1

1
2
3
4
5
6
7

# 解题思路

思路一样很简单，循环过程中如果找到目标值了就立刻返回其位置，否则当前的mid一定被排除在搜索区间之外，对应地right和left等于mid-1/mid+1。最后一次当left=right时如果mid值仍不等于target（其实一定小于target）则返回left。

public int searchInsert(int[] nums, int target) {
    if (nums==null||nums.length==0) return 0;
    int left=0,right=nums.length-1;
    while (left <= right) {
        int mid=left+((right-left)>>1);
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

看了上面的两题，似乎让人觉得二分查找不过如此，但其实我在做的时候在细节上还是栽了不少跟头的，一般二分查找的框架为：

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) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

其中...的位置就容易出错，想要区分清楚这些细节可以点击二分查找详解 (opens new window)。

首先left和right初始化时的取值就决定了搜索区间的性质，一般left取搜索开始的第一个位置（例如上面第一题从1开始，第二题从0开始），而right的取值有nums.length-1和nums.length两种，分别能取到和取不到，这样决定的搜索区间就分别为[left,right]闭区间和[left,right)左闭右开。

这就决定了while循环的终止条件前者为left>right，后者为left=right；同时也决定了nums[mid]不等于目标值时两者的搜索区间收缩范围，前者为(left=mid+1或right=mid-1)，后者为(left=mid+1或right=mid)。

注意点	闭区间查找	左闭右开查找
区间定义	left=0,right=n-1	left=0,right=n
循环条件	while(`left<=right`)	while(`left<right`)
`nums[mid]<target`:收缩左边界	left=mid+1	left=mid+1
`nums[mid]>target`:收缩右边界	right=mid-1	right=mid

关于最后应当返回什么值的问题：

如果仅仅是查找目标数的下标，如果存在的话返回-1，那么在if (nums[mid] == target)下返回下标，最后返回-1；
如果排序数组中可能有多个相同的目标值，而这时又要求查找相同目标值的左右边界，那么在if (nums[mid] == target)下就不能返回下标而是应该收缩查找范围继续查找。
- 如果是查找左边界，那么在if (nums[mid] == target)下不返回而是锁定左侧边界right=mid-1（闭区间）或right=mid（左闭右开），以确保剩下的搜索区间外部右边是当前找到的最左边界。继续在剩下的区间内搜索是否有目标值，没有的话最终left=right+1（闭区间）或left=right（左闭右开）都有left=mid，left就是最左的目标值。
  
  最后，检查left越界的情况。不论是闭区间（最终left=right+1）还是左闭右开（最终left=right），如果target大于数组中任意数的话最终left=n会越界，如果target小于数组中任意数的话最终left仍然是0但nums[left]!=target，所以要检查：
```
if (left >= nums.length || nums[left] != target)
    return -1;
return left;
```
  1
  2
  3
- 如果是查找右边界，原理相同。在if (nums[mid] == target)下锁定已找到的右侧边界left=mid+1（闭区间、左闭右开都是），并继续查找剩下的搜索区间，没有目标值时最终nums[left-1]就是最右侧的边界。
  
  最后检查left越界情况（我们使用left而不是right来表达右边界是因为闭区间和左闭右开情况下都是nums[left-1]为右边界，使用right的话要根据两种方式作出区分）。left的取值范围是[0, nums.length]则left-1的取值范围是[-1,nums.length-1]，target小于数组中任意数的时候左边有越界的风险，target大于数组中任意数的时候left-1=nums.length-1但nums[left-1] ！= target：
```
if (left == 0) return -1;
return nums[left-1] == target ? (left-1) : -1;
```
  1
  2

相信熟悉了这些知识就可以摸清二分查找的细节了。

Wallace's Blog

Choose mode