二分搜索返回错误值排查：输入10/大数时输出0如何修正？

我编写的C语言二分搜索代码如下，当输入10（对应数组下标9）或11这类大于数组最大值的数时，程序总是输出0。需要修改代码，使输入10时返回下标9，输入11时提示“Missed”。

原代码：

#include <stdio.h>

int binary_search(int arr[], int x, int sz)
{
    int left = 0;
    int right = sz - 1;
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (arr[mid] < x)
        {
            left = mid + 1;
        }
        else if (arr[mid] > x)
        {
            right = mid - 1;
        }
        else
        {
            return mid;
        }
    }
}

int main()
{
    int arr1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int n;
    int sz1 = sizeof(arr1) / sizeof(arr1[0]);
    printf("Enter the number you want：");
    scanf_s("%d", &n);
    int ret = binary_search(arr1, n, sz1);
    if (ret == -1)
    {
        printf("Missed");
    }
    else
    {
        printf("%d
", ret);
    }
    return 0;
}

问题分析 #

1. 循环条件left < right会漏掉left == right的情况：当目标是数组最后一个元素时，循环结束后未检查该位置元素，函数无明确返回值，导致返回随机值（此处为0）。
2. 函数未找到目标时没有返回-1，main中判断ret == -1不成立，错误输出下标。

修改后的代码 #

#include <stdio.h>

int binary_search(int arr[], int x, int sz)
{
    int left = 0;
    int right = sz - 1;
    // 修改循环条件为left <= right，覆盖所有元素位置
    while (left <= right)
    {
        // 用left + (right - left)/2替代(left+right)/2，避免数值溢出
        int mid = left + (right - left) / 2;
        if (arr[mid] < x)
        {
            left = mid + 1;
        }
        else if (arr[mid] > x)
        {
            right = mid - 1;
        }
        else
        {
            return mid; // 找到目标，返回对应下标
        }
    }
    // 循环结束未找到目标，返回-1
    return -1;
}

int main()
{
    int arr1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int n;
    int sz1 = sizeof(arr1) / sizeof(arr1[0]);
    printf("Enter the number you want：");
    scanf_s("%d", &n);
    int ret = binary_search(arr1, n, sz1);
    if (ret == -1)
    {
        printf("Missed\n");
    }
    else
    {
        printf("%d\n", ret); // 修正换行符，保证输出格式正确
    }
    return 0;
}

修改说明 #

• 调整循环条件为left <= right，确保数组中所有元素都能被检查到，包括最后一个元素。
• 循环结束后添加return -1，明确未找到目标时的返回值，配合main中的判断逻辑输出正确提示。
• 优化mid的计算方式，避免left + right数值过大导致的溢出问题，这是二分搜索的规范写法。
• 修正printf中的换行符，保证输出内容格式清晰。

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