深入了解二分查找法

对很多人来说,二分查找法并不难,是一种十分直观的算法.但是很多时候没有办法一次写好,因为其中包含了很多的细节.

正如KMP作者之一所说:

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

简单翻译就是,细节很简单,细节是魔鬼.

本文会探索几个常用的二分查找场景:如寻找一个数,寻找左侧边界,寻找右侧边界.

寻找一个数

寻找一个数基本上就是二分查找最常用的场景了,给定一个有序数组,来寻找一个给定的数,如果找到则给出,找不到则返回-1.

在这里,直接给出二分查找算法的直接实现,参考Leetcode704

class Solution {
    public int search(int[] nums, int target) {
        int i = 0;
        int j = nums.length-1;
        int mid = (i+j) / 2;
        while(i<=j){
            if(target == nums[mid]){
                return mid;
            }
            if(target>nums[mid]){
                i = mid+1;
            }else{
                j = mid-1;
            }
            mid = (i+j)/2;
        }
        return -1;
    }
}

其中,时间复杂度是O(logn),空间复杂度是O(1)

其中,有一些细节问题需要说明:

1. 为什么 while 循环的条件中是 <=，而不是 < ？

答：因为初始化 right 的赋值是 nums.length-1，即最后一个元素的索引，而不是 nums.length。

这二者可能出现在不同功能的二分查找中，区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)，因为索引大小为 nums.length 是越界的。

我们这个算法中使用的是前者 [left, right] 两端都闭的区间。这个区间其实就是每次进行搜索的区间，我们不妨称为「搜索区间」。

什么时候可以停止呢?自然是在找到了这个数之后就可以停止了

if(target == nums[mid]){
                return mid;
            }

如果没有找到这个数,会发生什么情况呢?这个就是我们上面说到的为什么需要用i<=j的条件了,如果没有找到这个数,那么我们设定的就是i=mid+1,或者j=mid-1,也就是超出了搜索空间的范围.

2. 为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？

答：这也是二分查找的一个难点，不过只要你能理解前面的内容，就能够很容易判断。

刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，如何确定下一步的搜索区间呢？

当然是 [left, mid - 1] 或者 [mid + 1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。

3. 此算法有什么缺陷？

答：至此，你应该已经掌握了该算法的所有细节，以及这样处理的原因。但是，这个算法存在局限性。

比如说给你有序数组 nums = [1,2,2,2,3]，target = 2，此算法返回的索引是 22，没错。但是如果我想得到 target 的左侧边界，即索引 11，或者我想得到 target 的右侧边界，即索引 33，这样的话此算法是无法处理的。这就引入我们下一个问题了

寻找左右边界的二分查找

直接看代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int i = 0;
        int j = nums.length-1;
        int mid = (i+j) / 2;
        while(i<=j){
            if(target == nums[mid]){
                return confirmRange(nums,mid);
            }
            if(target>nums[mid]){
                i = mid+1;
            }else{
                j = mid-1;
            }
            mid = (i+j)/2;
        }
        return new int[]{-1,-1};
    }

    public int[] confirmRange(int[] nums,int index){
        int i = index;
        int j = index;
        while(i>=0 && nums[i]==nums[index]){
            i--;
        }
        while(j<=nums.length-1 && nums[j]==nums[index]){
            j++;
        }
        return new int[]{i+1,j-1};
    }
}

在前面,我们直接使用二分查找的办法来寻找符合目标值的任意一个索引,查找到之后,用线性探测的办法前后寻找边界.

可能有人会认为在线性探测的部分会十分耗时,但是实际上,由于探测到了之后区间已经变得相对较小,使用二叉查找和线性探测的时间复杂度都不会很高.

不过,有的时候,还是使用边界的二分查找会更加方便.

其算法具体来说,就是执行如下步骤

1. 先使用二分查找法找到指定的数
2. 探测该数更靠近边界的下一个数是否相同
3. 如果相同,就指向下一个数,继续探测,如果不同,说明已经到头了,返回对应的位置

其编码如下

    public int getFirst(int[] array,int k,int start,int end){
         int mid = (start + end) / 2;
         while(start<=end){
             if(array[mid] == k){
                 if(mid == 0 || array[mid-1]!= k) return mid;
                 else mid--;
             }else if(array[mid]<k){
                 start = mid + 1;
                 mid = (start + end) / 2;
             }else{
                 end = mid - 1;
                 mid = (start + end) / 2;
             }
         }
         return -1;
     }

    public int getLast(int[] array,int k,int start,int end){
         int mid = (start + end) / 2;
         while(start<=end){
             if(array[mid] == k){
                 if(mid == array.length - 1 || array[mid+1]!= k) return mid;
                 else mid++;
             }else if(array[mid]<k){
                 start = mid + 1;
                 mid = (start + end) / 2;
             }else{
                 end = mid - 1;
                 mid = (start + end) / 2;
             }
         }
         return -1;
     }

#Java#