c - 我的二进制搜索实现有什么问题？

Question

#include <stdio.h>
int bsearch(int a[], int n, int lo, int hi) {
    int mid;
    mid = (hi + lo) / 2;
    if(a[mid] == n)
        return 1;
    else if(a[mid] > n)
        bsearch(a, n, lo, mid);
    else
        bsearch(a, n, mid, hi);
    return 0;
} 

int main(void) {
    int n, a[7] = {2, 4, 5, 67, 70, 80, 81};
    int hi = 6, lo = 0, j;
    scanf("%d", &n);
    j = bsearch(a, n, lo, hi);
    if(j)
        printf("Found");
    else
        printf("Not Found"); 
    return 0;
 }

input : 5 output: Not Found

谁能告诉我为什么会得到这个结果？

Answer 1

您需要解决几个大问题才能使其正常工作(请参阅以下代码注释中的详细信息)。

将您的二进制搜索函数更改为以下内容:

int bsearch(int a[], int n, int lo, int hi)
{
    // add base case
    if (high < low)  
        return 0; // not found 

    int mid;
    mid=(hi+lo)/2;
    if(a[mid]==n)
        return 1;
    else if(a[mid]>n)
        return bsearch(a,n,lo,mid-1); // add return
    else
        return bsearch(a,n,mid+1,hi); // add return
} 

---

P.S.: 根据您在 main() 主体中的用法，您实际上只需要返回 0/1 以指示包含值与否。我会建议您使用 bool 返回类型以使其更清晰。