关于upper函数的l < r 和二分查找 l <= r 的讨论
我之前一直对循环结束的边界问题很模糊，这章老师讲到upper时候 采用的while循环条件是（l < r）
之前的二分查找问题边界是（l <= r）。让我产生了疑惑，在视频中老师给出的解释是 upper函数中的
r 取得是data.length 所以当l 触及到 r的时候就应该结束了。 我从另一个角度也去思考了这个问题
1 | // upper : 找比target 大的 最小值<br>public static int upper(int[] data, int target) {<br> int l = 0, r = data.length;<br> while (l < r) {<br> int mid = l + (r-l)/2;<br> if (data[mid] <= target) {<br> l = mid + 1;<br> } else {<br> r = mid;<br> }<br> }<br> return l;<br>}<br> |
1 | private static int search(int[] arr, int target, int l, int r) {<br> while (l <= r) {<br> int mid = l + (r-l)/2;<br> if (arr[mid] == target)<br> return mid;<br> else if (arr[mid] < target) {<br> l = mid+1;<br> } else {<br> r = mid-1;<br> }<br> }<br> return -1;<br>}<br> |
当我把第一个条件的l < r 改为 l <= r的时候 代码陷入了死循环 其根本原因是因为 mid参数在r == l的时候 mid参数永远等于l 而在一些情况下程序会进入r=mid条件 造成r=l=mid 而约束条件又恰好符合的死循环 。
而反观二分查找为什么能够使用l <=r 呢 其实是因为在二分查找的循环中 r 和 l 维护的域必发生缩减，也就是从根本情况下避免了死循环的产生。所以我是不是可以简单的认为 ：在upper函数中之所以使用l < r 的约束 其实就是为了避免死循环的产生？
11
收起
正在回答 回答被采纳积分+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积分~
来为老师/同学的回答评分吧