Java岗算法面试——二分搜索算法及其变体

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

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

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

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>right，mid=(left+right)/2 也就是说，对于数组[2,3,4,6,7,8,9]如果查找的是5，则最终left会指向数组中最大小于5的数，也就是4，index 为2，right会指向最小大于5的数，也就是6,index为3，按照二分思想，此时mid应该指向4和5的中间，也就是如果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大的偏左的位置。

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

如上图，我们查找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处理，使得指针向右变收缩即可。

也就是当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条件结束的时候，三个关键位置的坐标在哪里，通过这三个坐标的特性，就能解决大部分问题。

作者：胖毛
链接：https://juejin.cn/post/6935248685303332901
来源：掘金