首页 文章

二进制搜索错误的输出,用于排序数组中的极端元素

提问于
浏览
0
#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的值是正确计算的,即使在数组极值的元素的情况下,但是对于极端元素,程序的输出仍然是错误的 . 任何人都可以指出它有什么问题吗?

1 回答

  • 2

    您在返回对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;
    }
    

相关问题