二進制搜索段錯誤

我想通過使用只有3個參數int值（我在找什麼），int值[]（數組），int n中以稍微非傳統的方式實現二進制搜索（數組的大小）。下面的代碼找到數字2，並認識到13不存在，但找不到像6或7這樣的數字。我認爲問題出現在最終的遞歸調用中。這可能是一個指針問題。我敢肯定，其餘的代碼工作正常。任何想我可能會出錯的想法，將不勝感激。二進制搜索段錯誤

#include <stdio.h> 
#include <stdbool.h> 

bool search(int value, int values[], int n); 

int main(void) 
{ 
    int value = 6; 
    int values[] = {1, 2, 3, 4, 5, 6, 7}; 
    int n = 7; 

    bool x = search(value, values, n); 

    if (x == true) 
     printf("found\n"); 
    else 
     printf("not found\n"); 
} 

bool search(int value, int values[], int n) 
{ 
    int midpoint = n/2; 

    if (n/2 <= 0) 
    { 
     return false; 
    } 
    if (value == values[midpoint]) 
    { 
     return true; 
    } 
    if (value < values[midpoint]) 
    { 
     return search(value, values, n/2); 
    } 
    else if (value > values[midpoint]) 
    { 
     return search(value, values, n/2); 
    } 

return false; 
}

來源

2016-09-21 Ryan

你需要像'values + n - n/2'（這與'values + n/2'不一樣）。 – user3386109

我記下我確定遵循，因爲values是數組的名稱。增加數量n/2似乎並不合理。儘管如此，我一定會玩弄它。非常感謝您的回覆！ – Ryan

'if（n/2 <= 0）'錯誤。 0是一個有效的數組索引。這就是爲什麼你的代碼在數組切片的開始處找不到任何值的原因。 – tofro

是的，問題是，當你調用與陣列的上半部分，你都要與膠印一樣

return search(value, values + (n + 1)/2, n/2);

請注意，我也跳過了中間元素通過它，你已經比較爲n單數的情況。您當然可以優化遞歸調用，始終注意長度的計算也是正確的。

來源

2016-09-21 07:11:44

這也有問題。 – deepmax

@Martin Sugioarto非常感謝！問題解決了！ – Ryan

二進制搜索段錯誤

回答

相關問題