我的二進制搜索實現有什麼問題？

#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; 
}

輸入：5輸出：未找到我的二進制搜索實現有什麼問題？

誰能告訴我爲什麼我得到這樣的結果？

來源

2014-02-11 user3298129

您是否知道stdlib.h中存在二進制搜索（具有相同名稱）？ http://www.cplusplus.com/reference/cstdlib/bsearch/ – Paulpro

在您的bsearch方法中，您是否想要在其他if-ifs中使用「return bsearch（a，n ..）」？ –

應該是'返回bsearch（a，n，lo，mid）;'，其他同上。如果找不到，則不指定條件。 – BLUEPIXY

您需要修復幾個大問題才能使其工作（請參閱下面的代碼註釋中的詳細信息）。

更改您的二進制搜索功能爲以下內容：

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 
}

PS：而基於main()身體您的使用情況，你實際上只需要返回0/1指示包含值或不。我會建議你使用bool返回類型使其更加清晰。

來源

2014-02-11 17:50:04 herohuyongtao

他的返回1沒有錯（如果根據他的主要用法）他只是試圖確定是否找到了值...但是，返回找到的地方更有用_IF_無效值返回表明沒有發現任何東西爲此，你可能應該把最後的'return 0;'改成'return -1;'（這會破壞OP主函數中的邏輯）。 – mah

@mah添加'return 1'使其一致。謝謝。 – herohuyongtao

'return'不會使其遞歸。事實上，它是遞歸的。它只是在遞歸調用中返回的值沒有做任何事情。 – ajay

添加「重返」遞歸調用，例如：

return bsearch(a,n,lo,mid);

否則，當您在bsearch返回1，它不會一路回到了主。

這將使其工作5。你有其他的錯誤，所以嘗試使用許多值，並使用IDE和/或printf來看看發生了什麼。祝好運並玩得開心點！

來源

2014-02-11 17:57:58

這是因爲您的bsearch函數中的return 0;語句始終執行，因爲您只是放棄了遞歸調用返回的值。在遞歸函數中，您必須首先確定基本情況。在這裏，您bsearch，基本情況要

low <= hi

這是必須是真實的，開始爲搜索值搜索的首要條件。如果此條件未得到滿足，則必須返回false，即0。

接下來，值返回函數調用是一個表達式，即它的值爲一個值。當你簡單地調用這個函數並且對結果不做任何處理時，你總是會掉到你函數中的最後一個return語句。在這裏，我列出了一些註釋以及bsearch函數中的說明。

int bsearch(int a[], int n, int lo, int hi) { 
    // first check for the base condition here 
    // if(hi < low) return 0; 

    int mid; 

    // can cause integer overflow. should be 
    // mid = lo + (hi - lo)/2; 

    mid = (hi + lo)/2; 
    if(a[mid] == n) 
     return 1; 
    else if(a[mid] > n) 

     // you are doing nothing with the value returned 
     // think of the function call as an expression 
     // return the value of the expression 
     // should be 
     // return besearch(a, n, lo, hi); 

     bsearch(a, n, lo, mid); 
    else 
     // same follows here 
     // should be 
     // return bsearch(a, n, mid, hi); 

     bsearch(a, n, mid, hi); 

    // finally you will always return 0 because this statement is always executed 
    // all cases have been taken care of. 
    // no return statement needed here 
    return 0; 
}

來源

2014-02-11 18:31:49 ajay

我的二進制搜索實現有什麼問題？

回答

相關問題