为什么需要特殊判断

Question

请问为什么最后求得的left可能是数目＜m的最小值？

Answer 1

吉他熊 2022-07-16 09:36:28

举两个例子：

l = 10, m = 2，石子距离分别为2 4 5 7 8

二分距离的时候，一开始left = 1，right = 10，之后每一步是这样的——

1. mid = (1 + 10) / 2 = 5，需要去掉2 4 7 8共4个，right = mid = 5

2. mid = (1 + 5) / 2 = 3，需要去掉2 5 8共3个，right = mid = 3

3. mid = (1 + 3) / 2 = 2，需要去掉5 8共2个，right = mid = 2（注意此时二分并未结束）

4. mid = (1 + 2) / 2 = 1，需要去掉0个，left = mid + 1 = 2，此时二分结束

这时候，left = 2是答案，不用特殊判断

把上面这组数据改一下——

l = 10, m = 2，石子距离分别为2 4 6 8

二分距离的时候，一开始left = 1，right = 10，之后每一步是这样的——

1. mid = (1 + 10) / 2 = 5，需要去掉2 4 8共4个，right = mid = 5

2. mid = (1 + 5) / 2 = 3，需要去掉2 6 8共3个，right = mid = 3（注意此时二分并未结束）

3. mid = (1 + 3) / 2 = 2，需要去掉0个（因为每个都刚好间隔2），left = mid + 1 = 3，二分结束

这时候，left = 3是答案吗？显然不是，最短距离为3的话，还是需要去掉至少3个石头才能达到目的

而最短距离为2的话，一个石头都不用去掉，所以这组数据并不存在刚好去掉2个石头就能满足的最短距离，这时候就需要这最后一步特殊判断了

• 提问者 慕雪4304792 #1

  谢谢老师的耐心解答，我还有一个问题，那就是我在学校学数据结构的时候，老师给的二分法是left = mid + 1，right = mid - 1，我看您两个视频当中都是习惯直接用right = mid，请问这两种有区别吗？
  对于为什么适用二分，您在视频中提到要符合单调性；同时，我们老师课上也提到二分搜索必须要是已经有序的序列，这是我对单调性这一要求的理解，其实本质上是一样的。

• 提问者 慕雪4304792 #2

  二分查找的时候，数组中下标为mid的值会与search值进行比较，假设数据是正序，如果a[mid] < search，那么说明小了，left = mid + 1；反之right = mid - 1。但无论如何，两种情况都是不需要再把mid本身框进区间内的，因为mid本身就是被“比较”的对象，根据“比较结果”决定下一次的区间是左or右半段。
  我感觉这里其实也一样，所取得的mid在本次if试探的时候就已经被验证了，那么在下一次二分的时候，就无需再框进区间里面了。

• 提问者 慕雪4304792 #3

  所以我觉得，这里写成right = mid - 1应该也没问题。并且我算了一下，发现不仅比较次数减少了，最重要的是，它好像对于您给的第二组数据不需要特殊判断了。不知道是不是个巧合，可能仍然存在需要特殊判断的情况？？

点开查看后面6条评论