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

Question

在Dennis M. Ritchie 和 Brian W. Kerninghan 所著的《C 编程语言》一书中的这个示例（第 3.3 节）中，我认为这段代码有问题，事实上，当我运行它时，它确实没有按预期工作。

这是书中的原始代码：

/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
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 */
}

因此，这个函数应该在整数数组中搜索整数，如果找到，该函数将返回其位置，否则将返回 -1。其中第一个明显的错误是 wile 循环中的测试low <= high，它在这个函数中将始终保持 True ，因此这个循环将无限期地运行并且永远不会结束（这就是我运行它时发生的情况，它陷入了困境显然是无限循环（编辑：如果 x 不在 v 中，否则它可以正常工作，但一个好的程序应该涵盖所有情况）），解决方案是删除测试的“或等于”部分，这意味着将其更改为low < high. 第二个错误是第一个if语句，因为当它发现x < v[mid]它设置high为mid + 1which显然是错误的，因为如果x值小于中间值（v数组已排序）那么x将位于小于中间的索引中索引，因此我们应该检查的范围是0tomid -1但事实并非如此，因为在书中他们将 mid 和 mid + 1 包含在我们知道它们大于 x 的范围内（因为 x < v[mid]） ，所以他们应该设置为高mid - 1。

所以，我的问题是：他们在这个例子中真的犯了错误，还是我误解了？如果他们这样做了，我所说的错误是否正确？最后，下面是该函数的实现以及我在上面的 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

K&R 第一版似乎包含以下代码，该代码确实存在缺陷并且可以永远循环：

/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
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; /* bug here */
        else if (x > v[mid])
            low = mid + 1;
        else /* found match */
            return mid;
    }
    return -1; /* no match */
}

K&R 第二版包括以下更正版本：

/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
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; /* correction here */
        else if (x > v[mid])
            low = mid + 1;
        else /* found match */
            return mid;
    }
    return -1; /* no match */
}