c++ - 二进制搜索排序数组中极端元素的错误输出

Question

#include <iostream>

using namespace std;

int bsearch(int x, int lo, int hi, int a[])
{
    if(lo <= hi) {
        int mid = lo + (hi - lo)/2;
        if(x == a[mid]) {
            cout<<mid<<endl;
           return mid;
        } else if(x < a[mid]) {
            hi = mid - 1;
            bsearch(x, lo, hi, a);
        } else {
            lo = mid + 1;
            bsearch(x, lo, hi, a);
        }
    }

    return -1;
}

main()
{
    int a[5] = {12, 13, 15, 18, 20};
    cout << bsearch(20, 0, 4, a);
}

以上是C++中二分查找的实现。我编写了一个函数来执行二进制搜索，该函数将排序的数组作为输入。在 main 函数中，我将一个排序整数数组作为参数传递给该函数。当我搜索不位于数组末端的元素时，该程序似乎工作正常，但给出了极端元素的错误输出。为了找出错误，我在函数体内包含了一个“cout”语句来打印出“mid”的值。令人惊讶的是，mid 的值计算正确，即使在数组极端元素的情况下，但程序的输出对于极端元素仍然是错误的。任何人都可以指出它有什么问题吗？

Answer 1

在对 bsearch 函数的递归调用中，您缺少 return 语句。

这似乎可行:

int bsearch(int x, int lo, int hi, int a[])
{
    if(lo <= hi)
    {
        int mid = lo + (hi - lo)/2;
        if(x == a[mid])
        {
           return mid;
        }
        else if(x < a[mid])
        {
            hi = mid - 1;
            return bsearch(x, lo, hi, a);
        }
        else
        {
            lo = mid + 1;
            return bsearch(x, lo, hi, a);
        }
    }
    return -1;
}