ステートメントが真の条件を認識していない場合？

Question

このバイナリ検索アルゴリズムに問題があります。変数の説明は次のとおりです。

値：

nで検索される配列：配列

高の要素数：ゼロによる最高要素（番号は配列

値[]内で検索されますゼロインデックス付け位置）

を検索されるアレイの一部によって（最小要素：ある配列の部分の索引付け位置）

ローを検索しました

私の問題は再帰ではありません。検索される配列の部分は「値」を中心とし、以下に示す条件が満たされている。問題は私のifステートメントがそうであると認識していないように見えるということです。私は条件が満たされていることを知っています。なぜなら、各再帰の値[高]、中間[値]、低[低]を印刷すると、

int search(int value, int values[], int n, int high, int low) 
{ 
    if (n <= 0) 
    { 
    return 1; 
    } 

    int middle = (high + low)/2; 

    ///condition #1 
    if (value == values[middle]) 
    { 
    return 0; 
    } 

    //conditions #2 and #3 (account for the maxes and mins of the array because the operation to find middle truncates) 
    else if (values[middle]==values[low] || values[middle]==values[high]) 
    { 
    return 0; 
    } 

    else if (value > values[middle]) 
    { 
     low = middle; 
     search(value, values, n, high, low); 
    } 

    else if (value < values[middle]) 
    { 
     high = middle; 
     search(value, values, n, high, low); 
    } 

    return 2; 
    } 

ここに間違いがありますか？このコードでは、密接

Answer 1

ルック：

else if (value > values[middle]) 
{ 
    low = middle; 
    search(value, values, n, high, low); 
} 

else if (value < values[middle]) 
{ 
    high = middle; 
    search(value, values, n, high, low); 
} 

通知は、これらのケースでは、あなたは再帰的search関数を呼び出すことができますが、戻り値と何もしません。つまり、searchによって返された値はすべて破棄され、コードは通常通りに続き、最終的には2を返します。あなたはif文の条件が発射されていないと思われる場合

else if (value > values[middle]) 
{ 
    low = middle; 
    return search(value, values, n, high, low); 
} 

else if (value < values[middle]) 
{ 
    high = middle; 
    return search(value, values, n, high, low); 
} 

は、一般的に言えば、それはゆっくりとデバッガで物事をステップ実行する価値があります：。これらreturn文に追加し、この問題を解決するには

そうすることで、（1）関数を再帰的に正しく呼び出すことができましたが、（2）返された値を返して破棄することに気づく可能性があります。

ここにコードで他の問題があるかもしれませんが、これは確かにあなたが対処する必要があるものです。それを動作させるように見えた

Answer 2

Quothcb3k

...他の問題はどうなるのでしょうか？

はここで、最小（必要に応じて、しかし、十分ではない）fixtemplatetypedefによって診断やテストハーネスを使用してコードです。ここで

#include <stdio.h> 

static 
int search(int value, int values[], int n, int high, int low) 
{ 
    if (n <= 0) 
    { 
     return 1; 
    } 

    int middle = (high + low)/2; 

    ///condition #1 
    if (value == values[middle]) 
    { 
     return 0; 
    } 

    // conditions #2 and #3 (account for the maxes and mins of the array because the operation to find middle truncates) 
    else if (values[middle] == values[low] || values[middle] == values[high]) 
    { 
     return 0; 
    } 

    else if (value > values[middle]) 
    { 
     low = middle; 
     return search(value, values, n, high, low); 
    } 

    else if (value < values[middle]) 
    { 
     high = middle; 
     return search(value, values, n, high, low); 
    } 

    return 2; 
} 

int main(void) 
{ 
    int data[15]; 
    for (int i = 0; i < 15; i++) 
     data[i] = 2 * i + 1; 

    printf("Data:"); 
    for (int i = 0; i < 15; i++) 
     printf("%3d", data[i]); 
    putchar('\n'); 

    for (int i = -1; i < 2 * 15 + 3; i++) 
     printf("Search for %2d - result %d\n", i, search(i, data, 15, 14, 0)); 
    return 0; 
} 

は出力です：

Data: 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 
Search for -1 - result 0 
Search for 0 - result 0 
Search for 1 - result 0 
Search for 2 - result 0 
Search for 3 - result 0 
Search for 4 - result 0 
Search for 5 - result 0 
Search for 6 - result 0 
Search for 7 - result 0 
Search for 8 - result 0 
Search for 9 - result 0 
Search for 10 - result 0 
Search for 11 - result 0 
Search for 12 - result 0 
Search for 13 - result 0 
Search for 14 - result 0 
Search for 15 - result 0 
Search for 16 - result 0 
Search for 17 - result 0 
Search for 18 - result 0 
Search for 19 - result 0 
Search for 20 - result 0 
Search for 21 - result 0 
Search for 22 - result 0 
Search for 23 - result 0 
Search for 24 - result 0 
Search for 25 - result 0 
Search for 26 - result 0 
Search for 27 - result 0 
Search for 28 - result 0 
Search for 29 - result 0 
Search for 30 - result 0 
Search for 31 - result 0 
Search for 32 - result 0 

それは関係なく、求められた値が配列中に存在するか否かの0を返しています。これは不正な動作です。

あなたはJon BentleyさんによってProgramming Pearlsを勉強する時間を取るべきです。さまざまな形式のバイナリ検索のテストの基礎をたくさんカバーしています。示されているテストハーネスは、彼が何を記述しているかのバリエーションです。また、 Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Brokenと読む時間もかかります。たぶん、他の多くの人が時間の経過とともにバイナリ検索を間違っているという安心感を得るべきでしょう。 （IIRC、バイナリ検索の最初のバージョンは1950年代に出版されましたが、1960年代初めまでは正しいバージョンが公開されていましたが、2006年の追加情報もあります）

else if (values[middle] == values[low] || values[middle] == values[high])の後にブロック内にprintf()と入力すると、失敗したはずのすべての検索に印刷されます。インターフェイスは、何が起きているのかを突き止めるのを難しくします。要素が見つかった場所、見つかった場所だけを報告しません。残りの問題に対処するために必要なデバッグとコードの変更を追加できます。 （ヒント：その状態はおそらくソリューションの一部ではありませんが、コードを削除すると、再帰的にチェックする範囲の範囲にないことがわかっていない値が削除されないので、コードは永続的なループに入ります。）

これは動作するようです - 最終else ifがfalseになることはありませんので、return 2;は（実行されることはありませんのでご注意

#include <stdio.h> 

static 
int search(int value, int values[], int n, int high, int low) 
{ 
    //if (n <= 0) 
    if (n <= 0 || high < low) 
    { 
     return 1; 
    } 

    int middle = (high + low)/2; 

    ///condition #1 
    if (value == values[middle]) 
    { 
     return 0; 
    } 

#if 0 
    // conditions #2 and #3 (account for the maxes and mins of the array because the operation to find middle truncates) 
    else if (values[middle] == values[low] || values[middle] == values[high]) 
    { 
     //printf(" (#2 || #3) "); 
     return 0; 
    } 
#endif 

    else if (value > values[middle]) 
    { 
     //low = middle; 
     low = middle + 1; 
     return search(value, values, n, high, low); 
    } 

    else if (value < values[middle]) 
    { 
     //high = middle; 
     high = middle - 1; 
     return search(value, values, n, high, low); 
    } 

    return 2; 
} 

int main(void) 
{ 
    int data[15]; 
    for (int i = 0; i < 15; i++) 
     data[i] = 2 * i + 1; 

    printf("Data:"); 
    for (int i = 0; i < 15; i++) 
     printf("%3d", data[i]); 
    putchar('\n'); 

    for (int i = -1; i < 2 * 15 + 3; i++) 
     printf("Search for %2d - result %d\n", i, search(i, data, 15, 14, 0)); 
    return 0; 
} 

出力：

Data: 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 
Search for -1 - result 1 
Search for 0 - result 1 
Search for 1 - result 0 
Search for 2 - result 1 
Search for 3 - result 0 
Search for 4 - result 1 
Search for 5 - result 0 
Search for 6 - result 1 
Search for 7 - result 0 
Search for 8 - result 1 
Search for 9 - result 0 
Search for 10 - result 1 
Search for 11 - result 0 
Search for 12 - result 1 
Search for 13 - result 0 
Search for 14 - result 1 
Search for 15 - result 0 
Search for 16 - result 1 
Search for 17 - result 0 
Search for 18 - result 1 
Search for 19 - result 0 
Search for 20 - result 1 
Search for 21 - result 0 
Search for 22 - result 1 
Search for 23 - result 0 
Search for 24 - result 1 
Search for 25 - result 0 
Search for 26 - result 1 
Search for 27 - result 0 
Search for 28 - result 1 
Search for 29 - result 0 
Search for 30 - result 1 
Search for 31 - result 1 
Search for 32 - result 1