javaee论坛

普通会员

225648

帖子

324

回复

338

积分

楼主
发表于 2019-10-31 13:27:02 | 查看: 122 | 回复: 1

在刷题的过程中,二分法用的还是挺多的,有时候超时了往往是你没有用上二分法,今天我就来稍微总结下用的最多的三种二分法搜索。

一、搜索和目标值相等的数

这一类是最简单的,例如对于数组arr={1,2,5,6,9},要我们搜索返回目标数target=6,这个时候我们需要返回6的下标i=3。代码如下

intbinarySearch(int[]arr,inttarget){intleft=0,right=arr.length-1;while(left<=right){intmid=left+(right-left)/2;if(arr[mid]==target)returnmid;elseif(arr[mid]<target)left=mid+1;elseright=mid-1;}return-1;}

不过这个有一个需要注意的点,就是很多人在求mid的时候,会这样写

mid=(left+right)/2;

其实这样写是有点小问题的,因为left+right有可能导致数值溢出,从而mid的计算就错误了,所以经常这样写的小伙伴要注意了,严谨的写法应该是这样写:

mid=left+(right-left)/2;二、查找第一个不小于目标值的数

查找第一个不小于目标的数,我觉得这类出现的频率是最高的,而且要注意,目标数并不一定就出现在数组中。

例如对于数组arr={1,2,5,6,9},目标数target=6,那么我们要返回下标i=4。

又如arr={0,1,2,2,2,3},target=2。我们要返回i=2。

代码如下

//intbinarySearch(int[]arr,inttarget){intleft=0,right=arr.length-1;while(left<right){intmid=left+(right-left)/2;if(arr[mid]<target){left=mid+1;}else{right=mid;}}returnright;}

在代码上,和第一种最大的区别就是right=mid-1变成right=mid了,至于为啥?自行脑补,随便找我上面举的例子模拟一下就行了。

对了,还有一种和查找第一个不小于目标值的数类似的题,就是找最后一个小于目标值的数。这很简单,直接返回right-1就可以了。

三、查找第一个大于目标值的数

查找第一个大于目标的数,我觉得这类出现的频率也是最高的,而且也要注意,目标数并不一定就出现在数组中。

例如对于数组arr={1,2,5,6,9},目标数target=6,那么我们要返回下标i=5。

又如arr={0,1,2,2,2,3},target=2。我们要返回i=5。

我们先来看下代码

intbinarySearch(int[]arr,inttarget){intleft=0,right=arr.length-1;while(left<right){intmid=left+(right-left)/2;if(arr[mid]<=target){left=mid+1;}else{right=mid;}}returnright;}

有木觉得和第二种类型的代码太像了,只需要在if语句里吧arr[mid]<target改成arr[mid]<=target即可。至于为啥?因为第一个不小于和第一个大于等于是同一个意思,但是这道题是第一个大于,不包括等于这种情况啊。所以把<改为<=即可。

总结

其实对于二分法的查找,有很多种类型,不过,代码的差别都不大,就是有可能大于改成大于等于。left/right=mid+1变成left/right=mid。所以有时也很容易出错,特别是脑子乱了的时候,所以我这里建议,选择一种自己喜欢的代码风格,然后每次做题的时候,的用你心中的那份模板代码。

当然,我上面说的这三种还是比较简单的,还有一些比较难的,就是target可能是动态更新的,而且left和right的更新也比较复杂,不过对于这种,在leetcode一般都是hard级别的题了。所以大家可以先把上面这三种掌握起来,不过你在做题时,并不会有直接说是哪种题型的话,甚至你都没有考虑到可以使用二分法来做,所以平时做题的时候可以多留意。

看完有收获?那么希望老铁给我个三连击

1、点赞,可以让更多的人看到这篇文章2、关注我的原创公众号『苦逼的码农』,第一时间阅读我的文章。公众号后台回复『电子书』送你一份电子书大礼包。3、也欢迎关注我的博客哦

作者info

作者:帅地,一位热爱写作的小伙原创公众号:『苦逼的码农』,以写了150多篇文章,专注于写算法、计算机基础知识等提升你内功的文章,期待你的关注。公众号后台回复『电子书』送你一份电子书大礼包。转载说明:务必注明来源(注明:来源于公众号:苦逼的码农,作者:帅地)


普通会员

0

帖子

300

回复

307

积分
沙发
发表于 2022-05-11 02:42:58

好好好

您需要登录后才可以回帖 登录 | 立即注册

触屏版| 电脑版

技术支持 历史网 V2.0 © 2016-2017