二元搜索使用遞歸

我不明白爲什麼這不會返回鍵，它似乎跳過了一步，我覺得邏輯是直的，如果midptr小於鍵，然後搜索右側，否則搜索左側。但它不返回鍵它返回-1。幫幫我？這裏是代碼和功能二元搜索使用遞歸

#include<iostream> 
using namespace std; 


int binsrch(int *raw, unsigned int size, int key); 




int main() 
{ 
    int raw[] = {1,3,5,7,11,23, 48}; 
    cout << binsrch(raw, 7, 11) << endl; 


    system("pause"); 
    return 0; 
} 



int binsrch(int *raw, unsigned int size, int key) 
{ 
    int *begptr, *endptr ,*midptr; 
//see if we already have the key 

if(*raw == key) 
    return key; 

begptr = raw; 
endptr = raw + (size - 1); 
midptr = raw + (size/2); 

cout << "#" <<*midptr << " size:" << size<< endl; 
if(*midptr == key) 
{ 
    return key; 
} 
else if(*midptr < key) //Search Right 
{ 
    cout << "#" <<*(midptr+1) << " size:" << size<< endl; 
    binsrch(midptr + 1, size/2, key); 
} 
else if(*midptr > key) //Search Left 
{ 
    cout << " #" <<*midptr << " size:" << size<< endl; 
    binsrch(begptr, size/2, key); 
} 

return -1; 
}

來源

2013-04-22 user2206227

@Paulpro：[C++版本]（http://www.cplusplus.com/reference/algorithm/binary_search/）會更好;它是類型安全的並且可能更快。 – 2013-04-22 18:24:14

真棒謝謝大家！ – user2206227 2013-04-22 18:31:44

您忘記了return聲明。您應該返回遞歸調用的結果：

binsrch(midptr + 1, size/2, key);

應該

return binsrch(midptr + 1, size/2, key);

否則您最初的通話將執行體的其餘部分，最後總是回到-1，除非你找到之前的關鍵第一次遞歸。

通過添加return語句，可以中斷遞歸調用的控制流（即，您不會返回「not found」值），並且您將最後一次返回值傳播到調用堆棧中，直到第一次調用，最後返回你想要的值。

來源

2013-04-22 18:11:45 Thibaut

它一切正常，但你不會返回正確的值。在else-if語句中，您將調用函數遞歸，但返回的值不會傳遞給初始調用！嘗試：

return binsrch(midptr + 1, size/2, key);

和

return binsrch(begptr, size/2, key);

這應該工作。

- 編輯：嗯，我想我已經放緩;）

來源

2013-04-22 18:20:53 CyDek

你也應該補充：

if(endptr == midptr) return -1;

計算endptr避免無限循環櫃面不陣列，例如搜索部件後21 ..等

來源

2013-04-22 18:20:57

二元搜索使用遞歸

回答

相關問題