《C程序设计语言》中二分查找binsearch代码是否存在错误？

问题背景 #

在Dennis M. Ritchie与Brian W. Kernighan所著《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。我认为存在两处错误：

• while循环条件low <= high会导致未找到目标时陷入死循环；
• 当x < v[mid]时设置high = mid + 1逻辑错误，因目标应在mid左侧，需将high设为mid - 1。

我修改后的代码 #

#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 */
}

疑问解答 #

1. 原书籍代码是否确实存在错误？ #

原代码确实存在逻辑错误，核心问题是当x < v[mid]时，high = mid + 1的赋值逻辑错误：

• 二分查找中，如果目标值小于v[mid]，说明目标只可能在[low, mid-1]区间内，把high设为mid+1会直接跳过mid左侧的有效区间，导致查找范围错误，甚至可能在未找到目标时出现死循环（比如当low == high且目标不在数组中时，循环条件low <= high成立，计算mid后又错误调整边界，导致low和high无法收敛）。
• 循环条件low <= high本身是二分查找的常用正确条件，错误根源不在这个条件，而是边界调整的逻辑错误。

2. 我的修正逻辑是否正确？ #

你的修正有对有错：

• 正确的部分：把x < v[mid]时的high = mid + 1改为high = mid - 1，这符合二分查找的边界收缩逻辑，能正确缩小查找范围。
• 错误的部分：将循环条件改为low < high是不必要的，甚至会引入新问题——当low == high时，循环直接退出，会漏掉对最后一个元素的检查。比如如果目标恰好是数组最后一个元素，且在循环过程中没有触发return mid，那么循环结束后直接返回-1，导致查找失败。

正确的修正应该是保留low <= high的循环条件，仅修改x < v[mid]时的high赋值为mid - 1，这样既不会漏掉元素检查，也能正确收缩边界。

3. 找到目标时执行return mid;后，是否会被循环外的return -1;覆盖返回值？ #

不会。return语句的作用是立即终止当前函数，并返回指定值。当在循环内执行return mid;时，函数会直接结束，不会再执行循环外的return -1;语句。只有当循环正常结束（即没有找到目标）时，才会执行最后的return -1;。

内容的提问来源于stack exchange，提问作者oabdullae