问题描述
我有一个任务来编写一个二分搜索，它返回我们正在寻找的值的第一次迭代。 我一直在网上做一些研究，我的搜索看起来很像我找到的东西，但我遇到了问题。 如果我将此代码传递给一个看起来像 {10,5,5,3,2} 的数组，它会在中间找到 5（它检查的第一件事）然后返回它。 但这不是 5 的第一次迭代，而是第二次。 我究竟做错了什么？ 这甚至可能吗？
提前致谢！
代码（我使用的是 Java）：
public static int binarySearch(int[] arr, int v){
int lo = 0;
int hi = arr.length-1;
while(lo <= hi){
int middle = (lo+hi)/2;
if(v == arr[middle]){
return middle;
}
else
{
if(v < arr[middle]){
lo = middle+1;
}
else
{
hi = middle-1;
}
}
}
return -1;
}
1楼
这是一个有效的修改算法。
public static int binarySearch(int[] arr, int v) {
int lo = -1;
int hi = arr.length - 1;
while (hi - lo > 1 ) {
int middle = (lo + hi) / 2;
if (arr[middle] > v) {
lo = middle;
} else {
hi = middle;
}
}
if (v == arr[hi]) {
return hi;
} else {
return -1;
}
}
关键点是：
- 区间 (lo, hi] 左侧不包含，右侧包含区间。
- 在每一步，我们都会丢弃一半的间隔。 当我们下降到一个元素时，我们就停止了。 尝试提前终止只能提供最小的性能提升，而它们通常会影响代码的易读性和/或引入错误。
-
当
arr[middle] = v我们分配hi = middle，从而丢弃右半部分。 这样做是安全的，因为我们不关心v超过middle任何出现。 我们确实关心arr[middle]，它可能是也可能不是第一次出现，正是出于这个原因，我们将 (lo, hi] 包含在右侧。如果在middle之前出现v，我们会发现它们在随后的迭代中。 -
作为旁注，更自然的定义
[0, n)包含在左侧，不包含在右侧，可用于查找v的最后一次出现。
根据我的经验，这种包含-排除间隔定义产生最短、最清晰和最通用的代码。 人们一直在努力改进它，但他们经常陷入困境。