在刷题的过程中,二分法用的还是挺多的,有时候超时了往往是你没有用上二分法,今天我就来稍微总结下用的最多的三种二分法搜索。
一、搜索和目标值相等的数
这一类是最简单的,例如对于数组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多篇文章,专注于写算法、计算机基础知识等提升你内功的文章,期待你的关注。公众号后台回复『电子书』送你一份电子书大礼包。转载说明:务必注明来源(注明:来源于公众号:苦逼的码农,作者:帅地)