关于upper函数的l < r 和二分查找 l <= r 的讨论

关于upper函数的l < r 和二分查找 l <= r 的讨论

我之前一直对循环结束的边界问题很模糊,这章老师讲到upper时候 采用的while循环条件是(l < r)

之前的二分查找问题边界是(l <= r)。让我产生了疑惑,在视频中老师给出的解释是 upper函数中的

r 取得是data.length 所以当l 触及到 r的时候就应该结束了。 我从另一个角度也去思考了这个问题

// upper : 找比target 大的 最小值
public static int upper(int[] data, int target) {
int l = 0, r = data.length;
while (l < r) {
int mid = l + (r-l)/2;
if (data[mid] <= target) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
​private static int search(int[] arr, int target, int l, int r) {
while (l <= r) {
int mid = l + (r-l)/2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target) {
l = mid+1;
} else {
r = mid-1;
}
}
return -1;
}

当我把第一个条件的l < r 改为 l <= r的时候 代码陷入了死循环 其根本原因是因为 mid参数在r == l的时候 mid参数永远等于l 而在一些情况下程序会进入r=mid条件 造成r=l=mid 而约束条件又恰好符合的死循环 。

而反观二分查找为什么能够使用l <=r 呢 其实是因为在二分查找的循环中 r 和 l 维护的域必发生缩减,也就是从根本情况下避免了死循环的产生。所以我是不是可以简单的认为 :在upper函数中之所以使用l < r 的约束 其实就是为了避免死循环的产生?

正在回答 回答被采纳积分+1

登陆购买课程后可参与讨论,去登陆

1回答
liuyubobobo 2021-04-12 20:09:28

你可以这么理解。是的,二分查找每轮循环保证了搜索空间的缩小,但是因为 upper 中有 r = mid 的条件,不保证搜搜空间的缩小。


但是从另一方面,upper 为什么不保证搜索空间的缩小?因为我们的搜索空间肯定有解!也就是你说的 l == r 的时候,一定就是解。这是 upper 和查找一个元素最大的不同。


所以,如果 l 和 r 碰上,肯定找到解了。因此,while(l < r) 就可以了。当然,如果你理解了这一点,也可以在 while 中判断,当 l == r 的时候返回这个解。


继续加油!:)

问题已解决,确定采纳
还有疑问,暂不采纳

恭喜解决一个难题,获得1积分~

来为老师/同学的回答评分吧

0 星
算法与数据结构
  • 参与学习       2583    人
  • 解答问题       1082    个

慕课网算法名师Liuyubobobo,5年集大成之作 从0到工作5年,算法与数据结构系统解决方案

了解课程
请稍等 ...
意见反馈 帮助中心 APP下载
官方微信

在线咨询

领取优惠

免费试听

领取大纲

扫描二维码,添加
你的专属老师