遞歸二進制搜索不能正常工作

int BinarySearch(int A[], int p, int r, int value) 
{ 
    int q = (p + r)/2; 

    if (A[q] == value) 
    { 
     return q; //value found 
    } 
    if (p == q) 
    { 
     return 0; //not found 
    } 
    if (A[q] > value) 
    { 
     return BinarySearch(A, p, q, value); 
    } 
    else 
    { 
     return BinarySearch(A, q + 1, r, value); 
    } 
} //binary search ends here

現在，問題是，無論何時我想搜索數組的最後一個元素，此代碼都會給出錯誤。任何人都可以請解釋爲什麼？遞歸二進制搜索不能正常工作

來源

2014-04-30 sunki08

這[行之有效的ideone（http://ideone.com/9NLYIj）。你能提供一組你的代碼失敗的數據嗎？ – dasblinkenlight

好的問題解決了我應該寫第二條件，如果在最後檢查p == q的條件現在它工作正常。順便說一句，任何改善此代碼的建議將不勝感激。 – sunki08

@ dasblinkenlight我正在使用dev C++ ide並輸入1 2 3 4 5的數組，並檢查5它說沒有找到 – sunki08

使搜索結束的情況下基於第一指數p末兩個索引r，

int BinarySearch(int A[], int p, int r, int value) 
{ 
    int q = (p + r)/2; 
    if(p > r) 
    { 
     return 0; 
    } 
    if (A[q] == value) 
    { 
     return q; //value found 
    } 
    if (A[q] > value) 
    { 
     return BinarySearch(A, p, q-1, value); 
    } 
    else 
    { 
     return BinarySearch(A, q + 1, r, value); 
    } 
}

來源

2014-04-30 10:43:56 LearningC

你好LearningC，你能解釋一下如何得到它的時間複雜度嗎？ – sunki08

@ sunki08好的。閱讀這些[link1]（http://stackoverflow.com/questions/8185079/how-to-calculate-binary-search-complexity）和[link2]（http://stackoverflow.com/questions/6094864/how-do - 您 - 計算最大-OH-的最二進制搜索算法）。搜索二進制搜索的時間複雜性，您將獲得許多關於導出時間複雜度的鏈接。 – LearningC

遞歸二進制搜索不能正常工作

回答

相關問題