値がソートされた配列に含まれている場合でも、Cのバイナリ検索は常にfalseを返します

Question

プログラミングの新機能。 Cでバイナリ検索を実装しようとしましたが、残念ながら正しく動作しません。値が配列内にあっても、私の関数は常にfalseを返します。プログラミングの初心者です。助けてください。

関数は次の入力を受け取ります。 "value" - 配列にある整数値。 "values" - ソートされた配列。 "n" - 配列内の整数の数。

bool search(int value, int values[], int n) 
{ 
    // recursive implementation of binary search 
    if (n % 2 == 0) 
    { 
     search_even(value, values, n); 
    } 
    else 
    { 
     search_odd(value, values, n); 
    } 
    return false; 
} 
bool search_even(int value, int values[], int n) 
{ 
    // binary search 
    if (n <= 0) 
    { 
     return false; 
    } 
    // check middle of array 
    else if (value == values[n/2]) 
    { 
     return true; 
    } 
    // search left half of sorted array 
    else if (value < values[n/2]) 
    { 
     int less_than_arr[n/2]; 
     for (int i = 0; i < n/2; i++) 
     { 
      less_than_arr[i] = values[i]; 
     } 
     search(value, less_than_arr, n/2); 
    } 
    // search right half of sorted array 
    else if (value > values[n/2]) 
    { 
     int more_than_arr[(n/2) - 1]; 
     for (int i = 0; i < (n/2) - 1; i++) 
     { 
      more_than_arr[i] = values[i + 1 + n/2]; 
     } 
     search(value, more_than_arr, n/2); 
    } 
    return false; 
} 

bool search_odd(int value, int values[], int n) 
{ 
    // binary search 
    if (n <= 0) 
    { 
     return false; 
    } 
    // check middle of array 
    else if (value == values[n/2]) 
    { 
     return true; 
    } 
    // search left half of sorted array 
    else if (value < values[n/2]) 
    { 
     int less_than_arr[n/2]; 
     for (int i = 0; i < n/2; i++) 
     { 
      less_than_arr[i] = values[i]; 
     } 
     search(value, less_than_arr, n/2); 
    } 
    // search right half of sorted array 
    else if (value > values[n/2]) 
    { 
     int more_than_arr[n/2]; 
     for (int i = 0; i < n/2; i++) 
     { 
      more_than_arr[i] = values[i + 1 + n/2]; 
     } 
     search(value, more_than_arr, n/2); 
    } 
    return false; 
} 

Answer 1

あなたは（再帰的に）search関数を呼び出しますが、呼び出しによって計算された値は返されません。

bool search(int value, int values[], int n) 
{ 
    // recursive implementation of binary search 
    if (n % 2 == 0) 
    { 
     search_even(value, values, n); 
    } 
    else 
    { 
     search_odd(value, values, n); 
    } 
    return false; 
} 

この関数常にリターン偽：を見てください。

search*(...)をreturn search*(...)に置き換える必要があります。その結果、コールの葉で決定された値が元の（最初の）コールに戻されます。

Answer 2

ジャン=バティストは、すでにあなたの関数の明らかな誤りを指摘しているが、より多くの問題があります。

あなたが検索するサブアレイのローカルコピーを作成します。これは必要ではなく、バイナリ検索は線形検索よりも遅くなります。

データのコピーは、通常、元の状態を維持しながら変更する場合にのみ必要です。検索機能はデータのみを検査します。厳密には、その事実を反映するために、あなたの引数int values[]はおそらくconst int values[]であるべきです。

Cでは、ポインタを最初の要素と配列の長さに渡す必要があります。配列は最初の要素へのポインタに減衰するので、次のようになります。

int val[4] = {2, 4, 7, 12}; 

search(3, val, 4); 

すでにそうです。

しかし、ここで便利なイディオムだ：あなたが位置kから始まる部分配列で渡したい場合には、使用：loはゼロです

より一般的に

search(3, val + k, 4 - k); 

、あなたは、配列スライス[lo, hi)を渡すことができますベースの包括的下限とhiのように排他的な上限である：

呼び出された関数で

search(3, val + lo, hi - lo); 

、インデックスは次いで[0, hi - lo)あろう。元の配列オフセットは失われます。あなたは元のサイズのマイナス、左側の列に1を足した大きさの差として右の配列のサイズを計算する場合

さらに、あなたはnn奇数と偶数の2例を区別する必要はありません。 ：

これにより

mid == n/2 
left = [0, mid) 
right = [mid + 1, n) 

、あなたの再帰的なバイナリ検索機能はなります：

bool search(int value, const int values[], int n) 
{ 
    if (n == 0) return false; 

    if (value < values[n/2]) { 
     return search(value, values, n/2); 
    } 

    if (value > values[n/2]) { 
     return search(value, values + n/2 + 1, n - n/2 - 1); 
    } 

    return true; 
}