关于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
你可以这么理解。是的,二分查找每轮循环保证了搜索空间的缩小,但是因为 upper 中有 r = mid 的条件,不保证搜搜空间的缩小。
但是从另一方面,upper 为什么不保证搜索空间的缩小?因为我们的搜索空间肯定有解!也就是你说的 l == r 的时候,一定就是解。这是 upper 和查找一个元素最大的不同。
所以,如果 l 和 r 碰上,肯定找到解了。因此,while(l < r) 就可以了。当然,如果你理解了这一点,也可以在 while 中判断,当 l == r 的时候返回这个解。
继续加油!:)
恭喜解决一个难题,获得1积分~
来为老师/同学的回答评分吧
0 星