您好,欢迎来到站长目录(28sn.com)!


聊一聊二分查找法

来源:网络整理 浏览:278次 时间:2021-09-20
前言

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

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

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

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

你清楚循环终止条件吗?

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

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

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

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

这个场景是最简单的场景,也是大家最熟悉的入门算法,即在数组中搜索一个指定的数字,如果存在返回索引,如果不存在返回-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]

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

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

    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的二分查找法专题中看一看,会很容易看懂其中的原理。

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

推荐站点

  • 我爱发烧音乐我爱发烧音乐

    我爱发烧音乐囊括了从流行音乐到古典音乐多个类型的音乐作品,专栏推荐最新的音乐,提供音乐排名榜单!可供免费线上收听音乐,歌曲流畅,音效极佳! 网站提供的钢琴以及二胡专栏,可供收听者,陶冶情操,改善心情,是难得的轻音乐典藏!

    www.520fs.com
  • 世纪音乐网世纪音乐网

    世纪音乐网是专业的在线音乐试听MP3下载网站。歌曲总计30余万首,收录了网上最新歌曲和流行音乐,DJ舞曲,非主流音乐,经典老歌,劲舞团歌曲,搞笑歌曲,儿童歌曲,英文歌曲等。是您上网听歌的最佳网站。

    www.ssjj.com
  • 杭州网杭州网

      杭州网是杭州地区唯一的新闻门户网站,由中共杭州市委宣传部、杭州日报报业集团和杭州广播电视集团共同组建的杭州网络传媒有限公司运营。

    www.hangzhou.com.cn
  • 深圳在线深圳在线

      深圳在线 www.szol.net是深圳本地最大、最早的地方生活资讯网站之一,网站名“深圳在线www.szol.net”由南方报业传媒集团编辑委员会总编辑、南方日报社总编辑、南方都市报总编辑、南方书画院名誉院长王春芙亲笔题名,深圳在线www.szol.net团队与深圳热线www.szonline.net、奥一网www.oeeee.com都源于全国最早成立于1996年的知名网络公司——深圳万用网。

    www.szol.net
  • 今题网今题网

     今题网- 中国领先的社区服务网,提供社区服务, 在线交友和商家推广服务,于2004年创建上线,公司现有员工超过百名。今题网自成立以来,凭借其独特的定位和丰富的社区交友功能, 凭借其团队超强的搜索引擎优化技术吸引超过千万的用户成为今题网的注册会员。

    www.jinti.com

鄂公网安备 42062502000001号