0%

二分查找算法总结

Posted on Edited on In ,

二分查找算法总结

二分查找思路很简单，从一个有序数组中对某个目标数进行折半查找，不断缩小范围，直到找到这个数。但二分查找实现的细节却有很多，很多时候不注意，结果就会很玄学。

基本模板如下：

1
int binarySearch(int[] nums, int target){
2
    int left=0, right=...;
3
    while(...){
4
  	     // mid=(left+right)/2相加结果有可能会溢出
5
  	     // 这里的left+(right-left)/2就可以避免这种情况
6
        int mid = left + (right-left)/2;
7
        if(nums[mid] == target){
8
    	   ...
9
        }else if(nums[mid] < target){
10
    	   left = ...
11
        }else if(nums[mid] > target){
12
            right = ...
13
        }
14
    }
15
    return ...;
16
}

其中...标记的地方，就是可能出现细节问题的地方。我们分别考虑二分查找的三种情况，分别是寻找一个数（基本的二分搜索）、寻找左侧边界的二分搜索以及寻找右侧边界的二分搜索。

##寻找一个数（基本的二分搜索）

1
int binarySearch(int[] nums, int target){
2
    int left=0, right=nums.length-1;
3
    while(left <= right){
4
        // mid=(left+right)/2相加结果有可能会溢出
5
        // 这里的left+(right-left)/2就可以避免这种情况
6
        int mid = left + (right-left)/2;
7
        if(nums[mid] == target){
8
            return mid;
9
        }else if(nums[mid] < target){
10
            left = mid + 1;
11
        }else if(nums[mid] > target){
12
            right = mid - 1;
13
        }
14
    }
15
    return -1;
16
}

或者

1
int binarySearch(int[] nums, int target){
2
    int left=0, right=nums.length;
3
    while(left < right){
4
        // mid=(left+right)/2相加结果有可能会溢出
5
        // 这里的left+(right-left)/2就可以避免这种情况
6
        int mid = left + (right-left)/2;
7
        if(nums[mid] == target){
8
            return mid;
9
        }else if(nums[mid] < target){
10
            left = mid + 1;
11
        }else if(nums[mid] > target){
12
            right = mid;
13
        }
14
    }
15
    return -1;
16
}

1.为什么一个是left<right，另一个是left<=right

注意两者的区别，这里引入一个搜索区间的概念。在第一段代码中，左边界为left=0，而右边界为right=nums.length-1，因此搜索区间为[left,right]，左闭右闭。而在第二段代码中，左边界为left=0，而右边界为right=nums.length，但数组下标最大为nums.length-1，因此搜索区间为[left,right)，左闭右开。这就导致了两者在while循环条件中的不同，第一段代码为while(left<=right)，循环终止条件是left=right+1，此时搜索区间为[right+1,right]，这时候区间为空，循环终止是正确的，但如果将循环条件改为while(left<right)，那么循环终止条件是left==right，这时候搜索区间为[right,right]，此时搜索区间还存在一个索引left，循环终止的话就会遗漏这个索引，因此会出错。

2.为什么一个right=mid-1，另一个是right=mid

这个问题也可以用搜索区间来回答，在第一段代码中，如果nums[mid]!=target，就要去两边搜索，这时候的搜索区间应该在[left,mid-1]和[mid+1,right]中选择，因为索引mid已经被考察过了。如果nums[mid]>target，说明中间数大于目标数，应该到左区间去搜索，那么right=mid-1。而在第二段代码中，如果nums[mid]!=target，搜索区间应该变为[left,mid)和[mid+1,right)。如果nums[mid]>target，说明中间数大于目标数，应该到左区间去搜索，那么right=mid。如果改为像第一段代码中的right=mid-1，那么左搜索区间就为[left,mid-1)，此时由于右边为开区间，搜索区间会遗漏一个数nums[mid-1]。

##寻找左侧边界的二分搜索

1
int left_bound(int[] nums, int target) {
2
    if (nums.length == 0) return -1;
3
    int left = 0;
4
    int right = nums.length; // 注意
5
    // 搜索区间为[left,right)
6
    while (left < right) { // 注意
7
        int mid = left + (right - left) / 2;
8
        // 搜索区间变为[left,mid)
9
        if (nums[mid] == target) {
10
            right = mid;
11
        } else if (nums[mid] < target) {
12
            // 搜索区间变为[mid+1,right)
13
            left = mid + 1;
14
        } else if (nums[mid] > target) {
15
            // 搜索区间变为[left,mid)
16
            right = mid; // 注意
17
        }
18
    }
19
    return left;
20
}

上面代码是搜索区间左闭右开的写法。为了可以寻找左侧边界，关键在于：

1
if (nums[mid] == target) {
2
    right = mid;
3
}

当搜索到目标数的时候，不是马上返回，而是缩小搜索区间的上界right，在区间[left,mid)中继续搜索，即不断向左搜索，达到锁定左侧边界的目的。

如果搜索不到target，那么返回的是target在有序数组中应该处于的位置索引。例如有序数组nums=[2,3,5,7],target=1，那么算法返回，说明target应该在数组索引0处，其他数字往后挪一位。

搜索区间左闭右闭的写法如下：

1
int left_bound(int[] nums, int target) {
2
    if (nums.length == 0) return -1;
3
    int left = 0;
4
    int right = nums.length-1; // 注意
5
    // 搜索区间为[left, right]
6
    while (left <= right) { // 注意
7
        int mid = left + (right - left) / 2;
8
        // 搜索区间变为[left, mid-1]
9
        if (nums[mid] == target) {
10
            right = mid - 1;
11
        } else if (nums[mid] < target) {
12
            // 搜索区间变为[mid+1, right]
13
            left = mid + 1;
14
        } else if (nums[mid] > target) {
15
            // 搜索区间变为[left, mid-1]
16
            right = mid - 1; // 注意
17
        }
18
    }
19
    return left;
20
}

寻找右侧边界的二分搜索

原理同寻找左侧边界的二分搜索，在找到目标数后，缩小搜索区间的下界left，在新的搜索区间不断搜索，即不断向右搜索，达到锁定右侧边界的目的。左闭右开的写法：

1
int right_bound(int[] nums, int target) {
2
    if (nums.length == 0) return -1;
3
    int left = 0, right = nums.length;
4
    // 搜索区间为[left, right)
5
    while (left < right) {
6
        int mid = (left + right) / 2;
7
        // 搜索区间变为[mid+1, right)
8
        if (nums[mid] == target) {
9
            left = mid + 1; // 注意
10
        } else if (nums[mid] < target) {
11
            // 搜索区间变为[mid+1, right)
12
            left = mid + 1;
13
        } else if (nums[mid] > target) {
14
            // 搜索区间变为[left, mid)
15
            right = mid;
16
        }
17
    }
18
    return left - 1; // 注意
19
}

关键点还是在这里

1
// 搜索区间变为[mid+1, right)
2
if (nums[mid] == target) {
3
    left = mid + 1; // 注意
4
}

循环终止条件是left==right，所以返回left-1还是right-1都一样，至于为什么要减1，由于在nums[mid]==target的时候，left=mid+1，就是说对left的更新一定是left=mid+1。当循环结束的时候，nums[left]一定不等于target，而nums[mid]即nums[left-1]可能等于target，因此需要减1。

左闭右闭的写法如下：

1
int right_bound(int[] nums, int target) {
2
    int left = 0, right = nums.length - 1;
3
    while (left <= right) {
4
        int mid = left + (right - left) / 2;
5
        if (nums[mid] < target) {
6
            left = mid + 1;
7
        } else if (nums[mid] > target) {
8
            right = mid - 1;
9
        } else if (nums[mid] == target) {
10
            // 这里改成收缩左侧边界即可
11
            left = mid + 1;
12
        }
13
    }
14
    return right;
15
}

这里返回的是right，因为循环终止的条件是left=right+1，即left-1=right，因此不需要减一，也可以写为left-1。

总结

二分搜索总体有左闭右闭和左闭右开两种写法，同时又可以分为基本二分搜索，寻找左侧边界的二分搜索和寻找右侧边界的二分搜索，框架相同，但细节不一样，用搜索区间的概念比较好理解。个人比较喜欢左闭右闭的写法。