欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找细节

程序员文章站 2024-03-20 17:19:16
...

总结

l=mid 区间长度为2死循环
r=mid 区间长度为1死循环

第一个<=x的数组下标

错误示范

if(nums[mid]<=x) l=mid;

这样会导致区间长度为2时死循环,即mid=l=m,r=m+1
且满足nums[m]<=x时
原因:因为mid是整数除法下取整的,所以mid始终是<=l的,即有可能等于l,而到最后l,r这个区间本身就是不断朝着满足<=x的方向进行搜索的区间,所以最后的l极有可能满足<=mid,所以最后l一直不变mid始终等于l等于m

while(l<=r){
	int mid=(l+r)>>1;
    if(nums[mid]<=x) l=mid;
    else r=mid-1;
 }

改进:为了避免为长度2时死循环则必须要=的时候l不再等于mid即
把等号和>符号放在一起,但这样就不是求<=x的第一个数了而是求<x的第一个数,这样就不会出现nums[mid=l]=x时l不动的情况了,但可能还是会出现nums[mid=l]<x时l不动的情况,所以不可行
即如果非要用l/r=mid,则判断条件不能取等号

while(l<=r){
	int mid=(l+r)>>1;
    if(nums[mid]<x) l=mid;
    else r=mid-1;//>=
 }

第一个>=x的数组下标

错误示范

if(nums[mid]>=x) r=mid;

这样会导致区间长度为1时死循环,mid=l=m
且满足nums[m]>=x时
原因:当只有一个搜索区间长度缩小到1时,因为是最优区间所以满足>=的条件所以r也一直不变导致mid不变,这样就不会出现nums[mid=r=l]=x时r不动的情况了

while(l<=r){
	int mid=(l+r)>>1;
    if(nums[mid]>=x) r=mid;
    else l=mid+1;
 }

改进:为了避免为长度1时死循环则必须要=的时候r不再等于mid即
把等号和<符号放在一起,但这样就不是求>=x的第一个数了而是求>x的第一个数,这样就不会出现区间长度为1时nums[mid=l=r]=x时l不动的情况了,但可能还是会出现nums[mid=l]<x时l不动的情况,所以不可行(但找最小值的时候可以,因为找最小值时区间长度为1则nums[mid]一定等于nums[r]所以可以跳过)
寻找旋转排序数组中的最小值
或者为了避免出现长度为1的区间循环条件改成l<r然后退出后单独判断l=r的情况

while(l<=r){
	int mid=(l+r)>>1;
    if(nums[mid]>x) r=mid;
    else l=mid+1;//<=
 }
相关标签: 二分 二分查找