老师, 为什么我按照以下的思路实现出来的 floor 函数逻辑是错的? 您帮我看看.
来源：5-1 二分查找法（Binary Search）
NewPan
2017-10-07
template<typename T>
int floor(T arr[], int n, T target) {
assert(n >= 0);
if (target < arr[0]) {
return -1;
}
int l = 0, r = n - 1, mid = 0;
while (l < r) {
mid = l + (r - l) / 2;
if (target <= arr[mid]) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
assert(l == r);
return l;
}看了你的 GitHub 上的代码不是很理解您的实现思路.
3回答
-
最大的问题在于，当arr[mid] < target的时候，此时arr[mid]有可能就是我们要求的floor值。比如数组[..., 1, 3, ...]，target=2；当arr[mid]指向1的时候，此时1就是这个数组对于2的floor值。但是你的逻辑依然让l=mid+1，相当于错过了这个值。应该让l=mid，也就是让l留在这里，然后继续观察看会不会有更合适的值。
当我们让l=mid的时候，会有一个很微妙的问题：当l=a，r=a+1这种情况的时候，由于下取整，mid计算出来仍然是l，此时我们的程序会进入一个死循环（随便找一个例子打印出循环每次的l，r和mid调试试试看：））。要打破这个死循环，我们需要在l=a, r=a+1这种情况下，计算出的mid是r的值，这样可以执行r=mid-1，进而在下次while循环里退出。所以在floor中，我们计算mid的方式是使用除不尽上取整的方式，即mid=(l+r+1)/2。为了防止溢出，我的代码写成mid = l + (r-l+1)/2。
这样计算出的arr[l]，将是比target小的最大的元素。之后我们来看arr[l+1]是不是target，如果是，我们的floor值取l+1的位置，否则就是l的位置。这是根据floor的定义来的。当然，在有些情况，我们可能就是想求出比target小的最大元素（即使arr中含有target），那么这一步就可以免掉了。
512017-10-07 -
NewPan
提问者
2017-10-07
// 使用向上取整避免死循环.
这句话不是很理解.
00 -
NewPan
提问者
2017-10-07
// 二分查找法, 在有序数组 arr 中, 查找 target. // 如果找到 target, 返回第一个 target 相应的索引 index. // 如果没有找到 target, 返回比 target 小的最大值相应的索引, 如果这个最大值有多个, 返回最大索引. // 如果这个 target 比整个数组的最小元素值还要小, 则不存在这个 target 的 floor 值, 返回 -1. template<typename T> int floor(T arr[], int n, T target) { assert(n >= 0); // 寻找比target小的最大索引. int l = -1, r = n - 1, mid = 0; while (l < r) { // 使用向上取整避免死循环. mid = l + (r - l + 1) / 2; if (target <= arr[mid]) { // 碰到和 target 相等的元素, 继续向前查找第一个和 target 相等的元素. r = mid - 1; } else { l = mid; // 因为上面加了 1, 所以这里不用加 1. } } // 如果该索引 +1 就是 target 本身, 该索引 +1 即为返回值. if( l + 1 < n && arr[l+1] == target ) return l + 1; // 否则, 该索引即为返回值. return l; }00
相似问题