• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

聊一聊二分查找法

开发技术 开发技术 6天前 10次浏览

前言

二分查找法是什么,难道是我们刚入行时候写的搜索算法吗?

还记得我们刚入行,接触算法的时候,一般都会从冒泡排序、二分查找开始入手算法,那小伙伴们会不会觉得这个算法太容易了,没有必要用一篇文章来讲解呢。

如果你有这样的疑问,那么王子问大家几个问题,看大家能否很容易的就回答的上。

你清楚二分查找法一般用于哪些查找场景吗?

你清楚循环终止条件吗?

什么时候使用<=,什么时候使用<这些你都清楚吗?

本文就与小伙伴们一起探讨几个最常用的二分查找场景:寻找一个数、寻找左侧边界、寻找右侧边界。

并对里面的实现细节做一个仔细的分析。

寻找一个数(最基本的二分查找法)

这个场景是最简单的场景,也是大家最熟悉的入门算法,即在数组中搜索一个指定的数字,如果存在返回索引,如果不存在返回-1.

直接看代码:

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) { // 注意
        int mid = left+(right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}

 针对于上边的代码,我们探讨几个问题。

 

1.为什么while循环中用的是<=而不是<?

因为我们初始化的right=nums.length-1,而不是nums.length。这两者的区别就是前者表示的是闭区间查找[left,right],后者表示的是开区间查找[left,right)。

因为我们选择的是[left,right]闭区间查找,所以while中的条件就是left<=right.

那么什么时候应该退出循环呢?当然是找到目标值了。

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

如果没有找到,就会通过while循环条件终止,并返回-1,而这个while循环中的条件,用大白话来讲就是代表搜索的区间是空的

while(left <= right)的终止条件是 left == right + 1,写成区间的形式就是 [right + 1, right],这种情况已经把数组中所有该寻找的值寻找过了,所以直接返回 -1 是没有问题的。

while(left < right)的终止条件是 left == right,写成区间的形式就是 [right, right],这时候搜索区间非空,还有一个数 right,但此时 while 循环终止了。也就是说索引 right被漏掉了,没有进行判断,如果这时候直接返回 -1 就可能出现错误。

这种错误我们只要在下边做些改动就可以解决。

//...
while(left < right) {
    // ...
}
return nums[left] == target ? left : -1;

 

2.为什么 left = mid + 1,right = mid – 1?

其实只要我们明白了刚才讨论的搜索区间原则,理解这个并不难。

我们的搜索区间是[left,right],那么当我们发现mid不是目标值的时候,应该怎么继续查找呢?当然是去查找[left,mid-1]或者是[mid+1,right]了,这个应该好理解吧。

所以如果我们nums[mid]<target的时候,代表要找的值在[mid+1,right]这一区间中,所以就有了left=mid+1。right=mid-1同理。

 

3.这样的写法是否可以解决所有二分查找的问题?

答案是不能的,如果给我们的nums=[1,3,3,3,4],target=3,由于是在中间二分查找,那返回的结果就是2。

但是如果我们要得到左侧边界和右侧边界,这种写法就不能实现了。

接下来我们分别说明左侧边界和右侧边界的写法。

 

左侧边界问题

首先我们要明白什么是左侧边界。

其实左侧边界可以理解成,这个数组中所有小于目标值的数字有几个,还是拿nums=[1,3,3,3,4],target=3来举例,它的左侧边界就是1,白话解释就是所有小于3的数字有1个。如果target=5,它的左侧边界就是5,也就是数组的长度,白话解释就是所有小于5的数字有5个。

好了,我们直接看代码:

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = left+( right - left ) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

 1.为什么没有返回 -1 的操作?如果 nums 中不存在 target 这个值,怎么办?

上边我们给大家白话解释了什么是左侧边界,那么什么时候会返回-1呢?就是没有找到目标数字的时候才会返回-1.

那么什么时候算是没有找到这个数字呢,一共有两种情况,一种情况是目标数字大于数组中的每个数字,这种情况下,left=right=nums.length。另一种情况是目标数字小于数组中的每个数字,也就是left=right=0,而且nums[0]!=target。

明白了上边的道理,我们就可以更改代码如下:

while (left < right) {
    //...
}
// target 比所有数都大
if (left == nums.length) return -1;
// 类似之前算法的处理方式
return nums[left] == target ? left : -1;

2为什么 left = mid + 1,right = mid ?

这个问题其实很好解释,我们之前的区间是[left,right]闭区间,而我们现在的区间是[left,right),所以当我们发现nums[mid]<target的时候,代表目标值在[left,mid)中,所以right=mid,而nums[mid]>target的时候,代表目标值在[mid+1,right)中,所以left=mid+1.

3.如何解释nums[mid]==target的时候,right=mid

其实这个就是解决左侧边界的主要判断条件。我们找到target的时候不是直接返回索引的,而是继续缩小范围并向左收缩的,也就是缩小[left,mid)的范围,所以就有了right=mid的写法。其实明白了这里,右侧边界也是同理,向右收缩搜索范围即可,写成left=mid+1就可以了。

 

右侧边界

有了左侧边界的经验,我们再来看右侧边界的问题就很容易了,直接看代码:

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = left+(right-left) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    if (left == nums.length) return -1;
    return nums[left-1] == target ? (left-1) : -1;// 注意
}

代码中已经标注了与左侧边界不同的地方。

1 left=mid+1刚才我们已经解释过了,不再说明。

2 为什么返回的值是left-1,而不是left

其实这个问题也好解释,因为本来我们要返回的值是mid,而在左侧边界问题中,最终结果的时候left=mid=right,所以返回left或者right都可以

而在右侧边界问题中,我们的left=mid+1=right,所以mid=left-1。

所以我们的返回值就是left-1了。

 

扩展

为了让大家对二分查找法印象更深刻,王子给大家分享一道扩展的题目算法,求x的平方根,题目如下:

聊一聊二分查找法

 

 

 这道题目其实也是可以用二分查找法做出来的。

求x的平方根,我们可以把搜素区间粗略的设定为[0,x],在这个区间中进行二分查找锁定目标就可以了。

那么什么时候算是找到了目标呢,肯定是mid*mid==target,或者是mid*mid<target,而且(mid+1)*(mid+1)>target,这两种情况下mid就是我们想要的结果。

有了思路,我们来看代码:

    public int mySqrt(int x) {
        // result用于存储结果
        int left = 0, right = x, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 这里一定要转换成long类型,否者如果数字过大会变成负数,影响结果
            if ((long) mid * mid <= x) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

这里我们引入中间变量result来存储想要的结果。

值得注意的就是mid*mid一定要强转成long,因为如果数字过大超过int的范围会变成负数,影响最终答案。

 

总结

至此,几个最常用的二分查找场景:寻找一个数、寻找左侧边界、寻找右侧边界,王子与大家就讨论完毕了。

通过本文,小伙伴们应该对于二分查找法的细节有了更深一步的了解。就算遇到二分查找法的变形,也可以运用这种解题思维独立思考并解决问题了。

看完本文,大家可以去LeeCode的二分查找法专题中看一看,会很容易看懂其中的原理。

小伙伴们去试一试吧,入果觉得本篇文章对你有所帮助,记得关注哦。

 

往期文章推荐:

中间件专辑:

什么是消息中间件?主要作用是什么?

常见的消息中间件有哪些?你们是怎么进行技术选型的?

你懂RocketMQ 的架构原理吗?

聊一聊RocketMQ的注册中心NameServer

Broker的主从架构是怎么实现的?

RocketMQ生产部署架构如何设计

RabbitMQ和Kafka的高可用集群原理

RocketMQ的发送模式和消费模式

算法专辑:

和同事谈谈Flood Fill 算法

详解股票买卖算法的最优解(一)

详解股票买卖算法的最优解(二)

聊一聊二分查找法


喜欢 (0)