二分问题中的“差一点”

首先引入一个问题

• 有一个从小到大排好序的数组，你要找到从右向左数第一个小于等于x的数字，应该怎么做？

我们很容易想到这样的一种二分做法，从右向左数第一个小于等于x的数字，也就是从左往右数最后一个小于等于x的数字，取到左边界和右边界，每次取到中间值和x比较，如果中间值小于等于x那么就把中间值当作左边界继续二分查找，也就是下面的C++代码

while(L<R) {int mid=(L+R)>>1;if(a[mid]<=x) L=mid;else R=mid-1;
}

你信心满满提交了代码，但是返回了TLE(即Time Limit Exceeded，时间超限)，一般二分法不会遇到超时问题，所以肯定是存在死循环，经过一番查找，发现有这样的一组数据我们这个代码将会陷入死循环

“差一点”问题（off-by-one）

现在 L=3,R=4,a[L]=3,a[R]=4，x为100，很显然我们的mid会取到3这个数，(3+4)>>2也就是(3+4)/2，又因为mid为整型，所以会去掉小数位取到3。然后3小于x，继续把L当作左边界，这就形成了一个死循环

要避免这个问题，其实也非常简单，我们只需要把中点计算公式变成 mid = (L + R + 1)/2 即可。在之前的中点计算公式 mid = (L + R)/2 中，我们如果遇到了中点不是整数的情况，则会把中点向下取整，因此在出现L + 1 == R 这种情况的时候就会始终有L == mid 从而引发问题。现在我们通过一个+1使得在中点不是整数的时候把中点向上取整，就可以避免这个问题

“一点”也不差

但是，如果我们使用mid = (L + R + 1)/2 为中点计算公式时，会在其他情况下出现“差一点”问题
所以我们只需要记住下面的规律就能一点也不差

• 如果代码中是用的L = M，把L不断往右push，那么M向上取整（M = (L + R + 1)/2）；
• 如果代码中是用的R = M，把R不断往左push，那么M向下取整（M = (L + R)/2）。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！