Dennis M. Ritchie 的《C 编程语言》一书中有关二分搜索的代码中存在错误？

Question

在这个来自 Dennis M. Ritchie 和 Brian W. Kerninghan 的《C 编程语言》书的示例（第 3.3 节）中，我认为这段代码有问题，事实上，当我运行它时，它确实无法正常工作预期的。因此，这个函数应该在整数数组中搜索整数，如果找到，该函数将返回其位置，否则将返回 -1。其中第一个明显的错误是 wile 循环中的测试 low <= high，它在这个函数中将始终保持 True，因此这个循环将无限期地运行并且永远不会结束（这就是我运行它时发生的情况，它显然陷入了无限循环），解决方案是删除测试的“或等于”部分，意味着将其更改为

low < high

。第二个错误是第一个

if

语句，因为当它发现

x < v[mid]

时，它将

high

设置为

mid + 1

这显然是错误的，因为如果 x 值小于中间值（v 数组已排序） ）那么 x 将位于小于中间索引的索引中，因此我们应该检查的范围将是

0

到

mid -1

但事实并非如此，因为在书中他们将 mid 和 mid + 1 包含在我们知道它们大于 x 的范围（因为 x

mid - 1

相反。< v[mid]), so they should have set high to 所以，我的问题是：在这个例子中他们真的犯了错误，还是我误解了？如果他们这样做了，我所说的错误是否正确？最后，这是该函数的实现以及我在上面的 C 代码中所述的更正（当我执行它时，它按预期工作）：

#include <stdio.h>

int binsearch(int x, int v[], int n);

int main() {
    int n = 10, x = 25;
    int v[10] = {0, 5, 10, 19, 20, 21, 22, 23, 25, 70};
    int position = binsearch(x, v, n) + 1;
    if (position) /*equivalent to (position != 0) since position will equal 0 when binsearch returns -1*/
        printf("x is at: %d", position);
    else
        printf("x is not found.");
    return 0;
}

int binsearch(int x, int v[], int n) {
    int low, high ,mid;
    low = 0;
    high = n - 1;
    while (low < high) {
        mid = (low + high) / 2;
        if (x < v[mid])
            high = mid - 1;
        else if (x > v[mid])
            low = mid + 1;
        else /* found match */
            return mid;
    }
    return -1; /* no match */
}

最后一个问题，当 x 确实在 v 中时，当找到对应的索引时，它会在 

return mid;

语句中返回，但是当我们跳出 while 循环时，我们发现 -1 也会返回，那不是会覆盖 while 循环的返回值吗？

Answer 1

最后一个问题，当 x 确实在 v 中时， 会找到对应的索引并在return中返回 中;语句，但是当我们跳出 while 循环时，我们发现 -1 也会被返回，那不是会覆盖返回的 while 循环的值？

不，当函数到达

return

语句时，它会终止执行并返回到调用者。您误解了函数的工作原理。

当你在火车上时，你把它留在A站。火车继续前往B站。你可以把它留在那儿吗？不 - 因为你不再在火车上了。