C語言中的二進制搜索總是回傳FALSE

我根據維基百科的偽代碼用C語言寫了一個二進制搜索程式，但它在處理只有一個元素的陣列時也一直回傳錯誤。我不知道它哪里出了問題。希望得到任何幫助。

這是個編碼挑戰，所以我沒有自己寫測驗程式。

編輯：該函式被測驗如下：

int arr[] = {6}; size_t length = sizeof（arr）/sizeof（*arr）。 TEST_ASSER((&arr[0] == binary_search(6, arr, length)) 。 int *binary_search(int value, const int *arr, size_t length) { int L = 0; int R = length - 1; static int m; while(L <=R) { m = floor((L R) / 2) 。 if(arr[m] < value) { L = m 1; } else if（arr[m] > value） { R = m - 1。 } else { return （&m）; } } return 0; }

編輯：在我洗掉了原函式中的const項后，用下面的代碼作業了。謝謝你們的幫助！

int *binary_search(int value, int *arr, size_t length） {
    int L = 0;
    int R = length - 1;
    static int m;
    while(L <=R) {
        m = (L   R) / 2; //no floor needed
        if(arr[m] < value) {
            L = m   1;
        } else if（arr[m] > value） {
            R = m - 1;
        } else {
            return &arr[m];
        }
    }
    return 0; //未找到; }
}

uj5u.com熱心網友回復：

陣列的長度被宣告為具有size_t

int *binary_search(int value, const int *arr, size_t length)  {

因此在這個函式中，變數L、R和m也應該被宣告為具有size_t型別。

同樣使用函式floor

m = floor((L   R) / 2) 。

絕對沒有意義，因為運算式(L R) / 2具有整數型別int。

將變數m宣告為靜態的也沒有很大的意義。

該函式應該回傳找到的元素在陣列中的位置，如果沒有找到這樣的元素，則回傳陣列的大小。

在這個條件下

TEST_ASSER((&arr[0] == binary_search(6, arr, length) )。

這里比較了陣列arr的第一個元素的地址和靜態區域變數m的地址。很明顯，這些物件占據了不同的記憶體范圍。因此，該條件將總是評估為邏輯上的false。

例如，該函式可以通過以下方式宣告和定義，如下面的演示程式所示。

#include <stdio.h>

size_t binary_search( const int a[] 。size_t n, int value ）
{
    size_t low = 0, high = n;
    
    while ( low < high )
    {
        size_t middle = low   ( high - low ) / 2;
        
        if ( value < a[middle] )
        {
            高 = 中。
        }
        else if ( a[mid] < value )
        {
            low = middle   1;
        }
        else; }
        {
            return middle。
        }
    }
    
    return n;
}

int main（void） 
{
    int a[] = { 6 };
    const size_t N = sizeof( a ) / sizeof( *a ) 。
    
    int value = 6;
    
    size_t pos = binary_search( a, N, value ) 。
    
    if ( pos != N )
    {
        printf( "在位置%zu發現了值%d
", value, pos )。
    }
    else; }
    {
        printf( "未找到值%d。
", value )。
    }
    
    value = 5;
    
    pos = binary_search( a, N, value )。
    
    if ( pos != N )
    {
        printf( "在位置%zu發現了價值%d
", value, pos )。
    }
    else; }
    {
        printf( "未找到值%d。
", value )。
    }
    
    value = 7;
    
    pos = binary_search( a, N, value )。
    
    if ( pos != N )
    {
        printf( "在位置%zu發現了價值%d
", value, pos )。
    }
    else; }
    {
        printf( "未找到值%d。
", value )。
    }
    
    return 0;
}

程式輸出是

值6在0位置找到。
值5未被發現。
沒有發現值7。

另一種方法是定義該函式，使其回傳一個指向陣列中找到的元素的指標，如果沒有找到這樣的元素，則回傳NULL。

下面是一個更有示范性的程式。

#include <stdio.h>

int * binary_search( const int a[] 。size_t n, int value ）
{
    size_t low = 0, high = n;
    
    while ( low < high )
    {
        size_t middle = low   ( high - low ) / 2;
        
        if ( value < a[middle] )
        {
            高 = 中。
        }
        else if ( a[mid] < value )
        {
            low = middle   1;
        }
        else; }
        {
            return ( int * ) ( a   middle ) 。
        }
    
    
    return NULL;
}

int main（void） 
{
    int a[] = { 6 };
    const size_t N = sizeof( a ) / sizeof( *a ) 。
    
    int value = 6;
    
    int *pos = binary_search( a, N, value ) 。
    
    if ( pos != NULL )
    {
        printf( "在位置%tu發現了價值%d
", value, pos - a )。
    }
    else; }
    {
        printf( "沒有找到 %d 的值。
", value )。
    }
    
    value = 5;
    
    pos = binary_search( a, N, value )。
    
    if ( pos != NULL )
    {
        printf( "在位置%tu發現價值%d
", value, pos - a )。
    }
    else; }
    {
        printf( "沒有找到 %d 的值。
", value )。
    }
    
    value = 7;
    
    pos = binary_search( a, N, value )。
    
    if ( pos != NULL )
    {
        printf( "在位置%tu發現了價值%d
", value, pos - a )。
    }
    else; }
    {
        printf( "沒有找到 %d 的值。
", value )。
    }
    
    return 0;
}

程式輸出與上面所示相同。

值6被發現在位置0。
值5未被發現。
值7未被發現。

uj5u.com熱心網友回復：

二進制搜索的邏輯應該是這樣的

如果while回圈被執行，并且沒有進入內部if(arr[m]==value)意味著元素不在串列中

uj5u.com熱心網友回復：

你的return陳述句回傳一個區域變數的地址。&m。這肯定是錯誤的，因為這個記憶體在函式回傳后不再被分配，而且它肯定不是你的驅動代碼中所期望的地址。

快速修復是return &arr[m]，但是就像評論中說的，回傳陣列元素的地址是很奇怪的。

只需回傳索引，并相應地調整函式的回傳型別，以及驅動代碼：

#include <stdio.h>


int binary_search(int值。const int *arr, size_t length)  {
    int L = 0;
    int R = length - 1;
    static int m;
    while(L <=R) {
        m = (L   R) / 2; //no floor needed
        if(arr[m] < value) {
            L = m   1;
        } else if（arr[m] > value） {
            R = m - 1;
        } else {
            return m;
        }
    }
    return -1; //未找到; }
}

int main（void） {
    printf("Hello World
"）。)
    int arr[] = { 6,  9,  13,  25};
    size_t length = sizeof（arr）/sizeof（*arr）。
    if (1 == binary_search(6, arr, length) {
        printf("ok!
"）。)
    }

    return 0;
}

標籤：

上一篇：有條件地使用影像

下一篇：演算法的分析和時間方程的建立？