二分查找细节
总结
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;//<=
}
上一篇: Android NDK Tombstone/Crash 分析
下一篇: Django实现下载文件功能