[刷题]重新审视二分查找算法的代码实现

重新审视二分查找

去年九月份投了人生第一份简历,百度地图公共出行部门的实习生,就抱着感受面试+碰运气的态度去面试了(结果可想而知,哈哈哈...Emm..面试官都挺好的,只不过三个部门的老大轮流面,每位大佬都面了一个小时可把我面死了,<ps:我猜测因为每个部门的老大都不想要我,所以都给别的部门来看一看> 而且我还是人生第一次面试, T.T) 其中第二位面试官问我的算法题让我手撕二分查找,当时还想,诶?这个面试官这么好,出的题好简单。现在刷了100道leetcode以后,再来审视这个问题发现,并不简单...

其实大家也可能有和我一样的想法,不就是二分查找吗,有什么可难的,
好,现在在没有复习的情况下我问大家几个问题,大家自查一下: 循环的条件是left<right还是left<=right?二分时是left=mid+1还是left=mid 同样的是right = mid-1还是right=mid?对于上面所有的问题:为什么这样做?

如果你能够对每一步的做法都道的清楚,那么恭喜你,这篇给像我这样的小菜菜看和复习的文章您可以跳过啦!

但是如果你和我一样,爆了粗口F&%^!k,好的,先握个手,我们先一起去学习一下liwei大佬如何理解这个问题(篇幅较长,耐心消化):
https://www.liwei.party/2019/...

正文

好了啦,其实我这篇文章也只是对他的一个自我消化,方便我日后复习,以及复习我失败的面试经历(卧薪尝胆啊懂不懂!)

liwei大佬的方法我觉得有这么三点比较重要:

  1. 不断夹逼目标值,通过left<right,避免不知道循环结束后选哪个边界的尴尬。
  2. 先写好判断的逻辑(即满足哪个条件一定会怎么怎么样,这一步往往是最重要也最难的部分)
  3. 根据逻辑选择mid(偶数时选左边还是右边)

多说无益,直接上题:

Leetcode704: 二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target,
写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

学会了之后先练个手,这很简单吧,我们这里把思考过程写清楚一点
这里目标值target也给出了(PS:有的题目需要自己思考目标值),
1.首先确定左边界和右边界 left = 0; right = nums.length-1;
2.写出while(left<right){}
3.确定分支逻辑.对于这一题我们可以想到如果nums[mid]<target,那么mid及mid左侧的元素里一定不存在目标值,我们缩减区间为left = mid+1;;那么相应的另一个分支为num[mid]>=target,这个分支的条件下 mid及mid左侧的元素都可能是target(或者说mid右侧的元素都不可能是target),我们缩减区间right = mid;(对于这一题,其实先从nums[mid]>target的角度思考是一样的啦)
4.我们的分支逻辑中包括了left=mid+1,为了避免死循环,我们需要定义mid = left + (right-left)/2 (也就是当剩下偶数个元素时,选择左边的那个mid,同理当你的二分逻辑为right=mid-1时,需要定义mid = left + (right-left+1)/2)
5.完成循环后,left==right,此时选left和right都是一样的.但由于target可能不存在数组中(可以简单思考一下这时候left指向了哪里),因此需要特判一下 return nums[left]==target?left:-1;
完整代码如下:

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

    }
}

来再做个应用题
Leetcode69: x的平方根

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:
输入: 4
输出: 2

示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数,小数部分将被舍去。

这一题求x的平方根取整,你当然可以用库函数,或者遍历O(N)的复杂度,哈哈哈,但是咱不是在练习嘛,来来来,我们用O(logN)时间复杂度,二分的方法做一下。
都是套路,继续上模板
1.首先确定左边界和右边界 left = 1; right = x;这里right为啥可以等于可以取到x了呢,因为一个数的平方根可能是它自己啊(不用看了,1,说的就是你)
2.写出while(left<right){}
3.确定分支逻辑.

注意,这里因为我们要找平方根,所以我们的目标是求一个mid使得( mid * mid ) == x .并且根据题意,小数部分被舍弃,即向下取整,那么使得i * i <=x 的 i 值都有可能是所求,但可以确定的是,使得i * i>x 的 i 值一定不是所求。
据此,我们可以写出分支逻辑:当mid * mid > x时,mid及mid右侧的元素一定不包括目标值,缩减区间为right = mid - 1;;那么类似于上一个题目,稍(套)加(用)思(模)考(板)另一else分支为left = mid

4.由于本题目的目标值一定存在,因此最后不需要特判返回即可.
完整代码如下:

class Solution {
    public int mySqrt(int x) {
        // 0 特判一下
        if(x==0) return 0;
        // 测试用例中存在大整数,因此用long
        long left = 1;
        long right = x;
        long mid;
        while (left<right){
            mid = left + (right-left+1)/2;
            if(mid*mid>x){
                right = mid-1;
            }
            else {
                left = mid;
            }
        }
        return (int)left;
    }
}

"老板!不过瘾,再来一碗酒(题)!"
"呦,客官,您看我们的招牌上写了‘三碗不过冈’啊.."
行吧,既然你这么要求了

Leetcode35: 搜索插入位置

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

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

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

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

其实这道题目和第一题大差不差,只不过这里数组里不存在目标值时还要求返回应该插入的位置.
因为逻辑判断的思路基本一致,所以不再赘述思考过程了,这里只讨论两个不一样的点
1.初始搜索区间为left=0; right=nums.lenght,因为需要找到插入的位置,因此需要把右边界扩展

你可能会想:诶?当right=nums.length难道这样不会越界吗?
答:可能会。区间收缩的过程中,可能收缩到这:[nums.length-1,nums.length], 而此时如果你选择了nums.length为mid 那么就会出现越界.但如果你选择了左边的为mid,紧接着left=mid+1, 此时left==right==nums.length,跳出循环,所以你选择左边的mid就不会出现越界

2.如果数组中不存在目标值,跳出循环时,边界指向哪里?

在第一题中我也让大家思考了这个问题。现在我们来讨论一下。可以肯定的是,此时两个边界值相同,且一定指向第一个小于目标值的元素或者第一个大于目标值的元素,那具体指向哪一个呢?答案是包含了mid的那个分支条件,更具体来说即left=mid 或right=mid中的其一,对应的即第一个小于目标值的元素或第一个大于目标值的元素.因为mid一直包含在这个分支中,这个分支条件也是我们最终夹逼的目标。

完整代码如下:

public class Solution{
    public static int searchInsert(int[] nums, int target) {
        if(nums.length==0) return 0;
        int left = 0;
        int right = nums.length;
        while (left<right){
            int mid = left + (right-left)/2;
            // 如果mid 小于target ,mid及mid左侧一定不是
            if(nums[mid]<target){
                left = mid+1;
            }
            // 如果 mid 大于等于target, mid或mid左侧可能是,但右侧一定不是
            else {
                right = mid;
            }
        }
        // 因为在变化的是左边界,而右边界包含了mid,
        // 最后边界会收缩到右边界的分支,即target的索引(找到了)或第一个>target的索引(没找到)
        // 而没找到时,这个索引刚好是应该插入的位置
        return left;
    }
}

这段代码等价于:

public int searchInsert(int[] nums, int target) {
        if(nums.length==0) return 0;
        if(target<nums[0]) return 0;
        if(target>nums[nums.length-1]) return nums.length;
        int left = 0;
        int right = nums.length-1;
        while (left<right){
            int mid = left + (right-left+1)/2;
            // 如果mid 大于target ,mid及mid右侧一定不是
            if(nums[mid]>target){
                right = mid-1;
            }
            // 如果 mid 小于等于target, mid或mid右侧可能是,但左侧一定不是
            else {
                left = mid;
            }
        }
        // 因为在变化的是右边界 所以最后区间会收缩到左边界的条件
        // 因此我们需要判断一下
        return nums[left]==target?left:left+1;
    }

第二段代码换了一个起始的思考过程,却同时带来了各种麻烦,我们需要各种特判来解决麻烦。造成麻烦的原因就在于跳出循环时,若该元素不存在,边界的指向位置在应插入位置的左侧。
大家可以通过nums=[1,2] target=0; nums=[1,2] target=3这个两个例子自己手动模拟一遍两种不同的方式,深刻理解边界的停留位置。
其实从分支条件来理解的话,第一段代码可以理解为夹逼到第一个大于等于目标值的位置,而这个位置刚好是插入位置,所以不需要各种特判;而第二段代码可以理解为夹逼到第一个小于等于目标值的位置,所以需要进行处理。

再来升级一下题目
Leetcode34: 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums,和一个目标值 target.
找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值,返回 [-1, -1]。

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

这次数组变为了可能有重复元素的数组,我们继续套用模板
1.确定查找区间[0,nums.length-1]
2.写出while(left<right){}
3.确定分支逻辑.

我们确定我们的目标值为:第一个等于目标元素的位置和最后一个等于目标元素的位置.我们先来分析第一个位置该如何夹逼
如果nums[mid]<target,那么mid及mid左侧一定不是目标值,那么有left = mid + 1;
因为有重复元素,我们这里也思考一下如果nums[mid]==target,该怎么做.假如现在出现了nums[mid]==target,因为我们要找第一个等于target的元素,那么mid及mid右侧的元素都可能是我们要找的元素,所以这个元素一定出现在 [ left, mid ] 的区间,即mid及mid左侧,因此我们需要砍掉mid右侧的区间,那么有right=mid;
再来看nums[mid]>target的情况,此时容易判断mid及mid右侧的元素一定不是,即right=mid-1;
我们合并两个砍掉右侧的逻辑,即num[mid]>=target时我们使right = mid;,不要忘记如何确定mid, 这样的情况下 mid = left + ( right - left ) / 2
从分支逻辑去理解最后的夹逼结果为:找到第一个大于等于target的元素(存在:等于,不存在:大于)
我们再用类似的思路思考如何夹逼最后一个位置。
如果nums[mid]<target,那么mid及mid左侧一定不是目标值,那么有left = mid + 1;
类似的如果nums[mid]>target,那么mid及mid右侧的元素一定不是,即right=mid-1;
主要区别在于nums[mid]==target时,而这时,我们要找的是最后一个元素,那么这个元素一定出现在 [ mid, right ] 的区间,因此需要砍掉左侧区间,即left = mid;
合并两个砍掉左侧区间的分支,即有nums[mid]<=target时,我们使left=mid;, 同时确定mid, right变动的情况下 mid = left + ( right - left + 1 ) / 2
从分支逻辑去理解最后的夹逼结果为:找到第一个小于等于target的元素(存在:等于,不存在:小于)

4.而题意指出,数组中可能不包含目标元素,而在找第一个元素的过程结束后,我们就可以通过nums[left]==target判断是否存在目标元素,如果不存在直接返回{-1,-1}即可.

大家可以通过这道题也品一品如果不存在目标元素,最后边界的落点应该在哪.

完整代码如下:

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = {-1,-1};
        if (nums.length==0) {
            return res;
        }
        int left = 0;
        int right = nums.length-1;
        // 求第一个等于目标值的位置
        while (left<right){
            int mid = left + (right-left)/2;
            // 如果mid小于目标值 那么第一个比目标值小的数一定在右侧,不包括mid
            if(nums[mid]<target){
                left = mid +1;
            }
            // 大于等于目标值, 可能在mid或mid左侧
            else {
                right = mid;
            }
        }
        // 假如不存在target 那么最后夹逼的结果会是第一个大于目标值的元素 所以这里需要判断一下
        if(nums[left]!=target){
            return res;
        }
        else {
            res[0]=left;
        }


        // 求最后一个等于目标值的位置
        left = 0;
        right = nums.length-1;
        while (left<right){
            int mid = left + (right-left+1)/2;
            // 如果mid大于目标值 那么所求元素一定在mid左侧
            if(nums[mid]>target){
                right = mid-1;
            }
            // 如果mid小于等于目标值, 那么所求元素可能在mid或mid右侧
            else {
                left = mid;
            }

        }
        // 元素一定存在,不需要特判
        res[1]= left;
        return res;
    }
}

其实二分法不只局限于完全有序的数组,在部分有序的数组中也可使用
Leetcode 153. 寻找旋转排序数组中的最小值
Leetcode 154. 寻找旋转排序数组中的最小值 II
其实两道题我用O(N)的方法,即遍历找变小的元素也能有100%的效率,第一题大家还是可以稍加思考做一下,我的建议是5分钟没思路就去看题解吧。主要是感受一下二分的条件是如此变通的。
而且第二题处理重复元素的方法比较trick,如果一时想不到思路,直接看题解就好了.

Liwei大佬在文章中还推荐了一些综合应用的题目,大家有兴趣可以尝试做一下
Leetcode 300. 最长上升子序列
Leetcode 287. 寻找重复数
Leetcode 658. 找到 K 个最接近的元素

评论

暂无评论