二分搜索算法及其变体

二分的思想很简单,但是代码的细节确很难理解,每次做算法遇到二分的变体,脑子里都是浆糊,当时理解了,后面又忘了,需要注意的细节太多太多了,网上有很多分析二分变体的博客,写的都很详细,但是总是阅后即忘。。。

今天碰巧又遇到了这类算法,痛定思痛,一定要解决这个问题。于是详细分析了下二分的思想,感觉豁然开朗,下面分享我认为最容易理解的解法:

想要写出正确的二分,必须明白以下几点:

  1. Java语言的除法结果,是直接截取整数的,比如(2+1)/2=1,也就是说在二分中是偏向左边,需要明白这一点用来定位最后mid到底在哪里。

  2. 由于是二分查找,因此不一定需要明确的知道两边的收缩条件,可以通过排除法,只要能明确值一定不在这边,那么值就一定在另外一边。

  3. 注意两个数相加溢出的问题,有些时候可以参考Arrays.binarySearch()中对(left+right)/2防止溢出的处理,使用(left+right)>>>1表示,这样处理对于因为溢出而负的值,可以强制转换为正数。但是对于本就是负数的处理,却是存在陷阱的,比如-1>>>1结果为Integer.MAX_VALUE,已经不是除以2的效果了。所以最好使用right+(left-right)/2代替

  4. 需要明白如果没有数组中确实不存在target, 那么最终 mid,left,right三个指标的位置应该在哪里。

    伪代码如下:

    while(left<=right){
       ...
       mid=(left+right)/2;    
    }
    

    可以看到 结束条件是left>rightmid=(left+right)/2

    也就是说,对于数组[2,3,4,6,7,8,9]如果查找的是5,则最终left会指向数组中最大小于5的数,也就是4,index 为2,right会指向最小大于5的数,也就是6,index为3,按照二分思想,此时mid应该指向45的中间,也就是如果5存在,则5应该存在的位置,但是由于上面第一条mid是偏向左边,因此mid会指向4,index为2。

明白上面的道理,就可以很好的运行二分以及各种二分变式。

标准二分

标准二分不用多说。

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

存在重复数据,查找第一次出现的坐标

标准二分虽然能查找到数据,但是有时候我们的需求是查找第一次出现的target的位置,比如:

[1,2,2,2,3,3,4,5,6] target=2,则返回index=1

如果通过标准二分查找,则在第二次折半的时候,就会直接返回,但是这并不是第一次出现的位置。

前面我们分析过,如果原数组中并不包含target,则mid会停留在左边比mid小,右边比mid大的偏左的位置。

image-20210302184132463

如上图所示,基于这个特性,我们就可以解决上面的问题,虽然数字可能重复,但是只要我们即使查找到具体的值之后依然一直向左边收缩,最终指针的位置一定就会停留在目前最大的小于target的位置。

image-20210302182516378

如上图,我们查找target为5,但是我们在查找到5之后,继续以5>target处理,此时区间则会继续向左边收缩,最终指针就会停留在4的位置,此时我们返回mid+1即可。

代码如下:

public int binarySearchFirst(int[] nums,int target){
    int left=0;
    int right = nums.length-1;
    int mid = right + (left - right)/2;
    while(left<=right){
        //查找到具体的值,继续向左收缩
        if(nums[mid]==target){
            right=mid-1;
        }else if(nums[mid] < target){
            left = mid +1;
        }else{
            right = mid -1;
        }

        mid = right + (left - right)/2;
    }
    //此时mid指向了最大小于target的左边,但是需要注意如果target比数组中所有的元素都大,则mid=nums.length-1,则mid+1会越界
    if(mid==nums.length-1){
        return -1;
    }
    //再判断mid+1是否为target,如果不是,说明数组中不存在这个元素
    return nums[mid+1]==target?mid+1:-1;

}

存在重复数据,查找最后一次出现的坐标

和上题有个对称的问题,就是如果存在重复的数据,则返回最后一次出现的坐标。比如:

[1,2,2,2,3,3,4,5,6] target=2,则返回index=3

其实,只要明白了上面的原理,我想代码应该很快就能写出来。刚刚我们处理当查找到5之后,将5做大于target处理,使得指针继续向左收缩,当需要查找最后一个出现的坐标时,就应该向6靠近,此时只需要将5做小于target处理,使得指针向右变收缩即可。

image-20210303092556063

也就是当nums[mid]==target时,做和nums[mid]<target相同的处理。同时需要注意,由于mid依然是靠左的,因此如果存在目标值,则它一定在6的左边,可能直接指向目标值5,也有可能指向4(5不存在的时候就会指向4)。

代码如下:

public int binarySearchLast(int[] nums,int target){
    int left=0;
    int right = nums.length-1;
    int mid = right + (left - right)/2;
    while(left<=right){
        //查找到具体的值,继续向右边收缩
        if(nums[mid]==target){
            left = mid +1;
        }else if(nums[mid] < target){
            left = mid +1;
        }else{
            right = mid -1;
        }

        mid = right + (left - right)/2;
    }
    //此时mid指向了最小大于target的左边,但是需要注意如果target比数组中所有的元素都小,则mid=-1,则nums[mid]会越界
    if(mid==-1){
        return -1;
    }
    //再判断mid是否为target,如果不是,说明数组中不存在这个元素
    return nums[mid]==target?mid:-1;
}

部分有序的二分查找

LeetCode上有个题,讲的是旋转数组的查找,一个原本有序的数组,经过旋转后,形成了一个新的数组,需要在这个数组上查找是否存在某个值。

比如:[4,5,6,7,1,2,3][8,1,2,3,4,5,6,7]

其实只要记得最开始所说的二分注意事项第二点,即可解答这个问题:

由于是二分查找,因此不一定需要明确的知道两边的收缩条件,可以通过排除法,只要能明确值一定不在这边,那么值就一定在另外一边。

仔细观察上面的数组可以发现,nums[mid]的左边或右边一定是有序的,只要判断出哪边是有序的,即可通过排查法找到target是否在有序的哪边,如果没在,那就一定是在另外一边,二分即可完成,无非是要多一些细节的处理而已。

总结

二分还有很多变体,但是万变不离其宗。一定需要理解如果二分一直运行到whlie条件结束的时候,三个关键位置的坐标在哪里,通过这三个坐标的特性,就能解决大部分问题。