二進制搜索沒有返回正確的值

我正在C++中實現二進制搜索算法，但算法沒有返回正確的值。代碼可以找到here。二進制搜索沒有返回正確的值

template<class T> 
int binary_search(T search_value, T search_array[]) { 

    int mid; /* The middle element of the remaining array to be searched. */ 
    int min = 0; /* The first index of the array. */ 
    /* This forumla gives us the size of the array. */ 
    int max = sizeof(search_array)/sizeof(search_array[0]); 

    /* Continue searching until min >= max. */ 
    while (min < max) { 
     /* Compute the value of mid using a formula that won't produce a number 
     * larger than the maximum allowed value of an integer. */ 
     mid = (max-min)/2 + min; 

     /* Depending the whether search_value is larger or smaller than the 
     * value of whatever is at search_array[mid], set one of mid and max 
     * equal to mid. */ 
     if (search_value > search_array[mid]) 
      min = mid + 1; 
     else if (search_value < search_array[mid]) 
      max = mid + 1; 
     else { 
      return mid; 
     } 
    } 

    return -1; 
}

鑑於數組{0，1，3，5，7，9}和搜索3，函數應返回2，3陣列中的索引。我的函數返回-1，這意味着3在數組中找不到。問題在哪裏？

來源

2012-02-13 mau5padd

開始似乎是一個非常瑣碎測試用例在調試器到步驟通過.. – Blorgbeard 2012-02-13 21:59:03

第一。在函數中使用sizeof-construction來接收數組大小是一個壞主意。在函數中再加一個參數，比如'int array_size' – mikithskegg 2012-02-13 22:00:57

你試過調試嗎？ – littleadv 2012-02-13 22:01:27

int max = sizeof(search_array)/sizeof(search_array[0]);

這種方法不適合計算數組的大小，它只適用於創建數組的函數。

將數組大小作爲函數的參數傳遞，這是最簡單的方法。

來源

2012-02-13 21:58:28 Saphrosit

這工作。只是爲了笑笑，有什麼更好的方法來計算一個數組的大小？實質上，我所做的只是將'sizeof（search_array）/ sizeof（search_array [0]）'移到'main'方法並將其傳遞給函數。 – mau5padd 2012-02-13 22:06:38

問題是你的函數中的'search_array'只是一個指向內存地址的指針，而不是一個數組，因此這種方法在你創建數組的函數（在這種情況下，主要）除外。沒有一種標準的方法來計算數組的大小，但是一種常見的方法是將其作爲函數的參數傳遞。其他方法可能包括使用特定的結構，比如'std :: vector'，它存儲數組的長度並消除在運行時計算它的問題。 – Saphrosit 2012-02-13 22:10:53

有一個在您的實現中的錯誤：

else if (search_value < search_array[mid]) 
    max = mid + 1;

應該是：

max = mid - 1;

來源

2012-02-13 21:58:32

雖然有一個錯誤，但這隻會降低性能，而不是故障的原因，對嗎？ – orlp 2012-02-13 22:01:10

可能不是。除非數組很小，否則它可能會訪問超出數組範圍的內存。 – 2012-02-13 22:01:51

我沒看到這個，謝謝指出！ – mau5padd 2012-02-13 22:08:05

這條線是至少一個問題：

int max = sizeof(search_array)/sizeof(search_array[0]);

數組不通過傳遞功能，所以你的聲明：

int binary_search(T search_value, T search_array[])

...是一樣的：

int binary_search(T search_value, T *search_array)

就這樣max是指針由元素的大小劃分的大小，因此，在最好的情況下也可能是多達6個，但大多數可能是0或1

我想在C++中，你可以通過引用傳遞數組和使用知道聲明的形式，這樣它的大小：

template <size_t array_length> 
void foo (const char (&data) [array_length]) 
{ 
    // ... 
}

來源

2012-02-13 21:59:12

此行不會做你認爲它母鹿S：

int max = sizeof(search_array)/sizeof(search_array[0]);

因爲數組時，傳遞給函數的自動衰減的指針，這將有效地等於這個：

int max = sizeof(void*)/sizeof(search_array[0]);

這是不是你想要的。請使用std::vector，其中存儲了您的大小或手動size_t array_length參數。

來源

2012-02-13 21:59:18 orlp

int max = sizeof(search_array)/sizeof(search_array[0]);

search_array是一個指針而不是數組。

函數原型中的參數類型爲T的數組會自動調整爲指向T的指針。

來源

2012-02-13 21:59:55 ouah

這條線是關於：

int max = sizeof(search_array)/sizeof(search_array[0]);

sizeof(search_array)將是一個指針的大小，4首或8個字節取決於平臺。通常，我儘量避免在變量上使用sizeof。它在類型上使用更好。例如，你的情況sizeof(T)。

來源

2012-02-13 22:00:32

你的最大值需要是少一個作爲索引從0

來源

2012-02-13 22:00:56 e7mac

二進制搜索沒有返回正確的值

回答

相關問題