-2

繰り返しを使用してこのバイナリ検索を行いましたが、答え（ブール値）を取得すると、繰り返しから抜け出す方法でつまずいて、関数から正しい答えを得ることができません。誰でも助けることができますか？コードについてコメントしてください。

// binary search
bool 
search(int value, int array[], int n)
{

    // the array has more than 1 item
    if (n > 1)
    {
        int m = (n/2);

        // compares the middle point to the value
        if (value == array [m])
            return true;

        // if the value given is lower than the middle point of the array
        if (value < array [m])
        {
            int *new_array = malloc (m * sizeof(int));

            // creating a new array with the lower half of the original one
            memcpy(new_array, array, m * sizeof(int));

            // recalling the function
            search (value, new_array, m);
        }


        // if the value given is greater than the middle point of the array
        else
        {
            int *new_array = malloc (m * sizeof(int));

            // creating a new array with the upper half of the original one
            memcpy(new_array, array + (m + 1), (m  * sizeof(int)));

            // recalling the function
            search (value, new_array, m);
        }
    }

    else if (n==1)
    {

        // comparing the one item array with the value
        if (array[0] == value)
            return true;

        else
            return false;

    }

    if (true)
        return true;

    else 
        return false;



}
4

3 に答える 3

0

amint で述べたように、配列をコピーすると、バイナリ検索を実行する目的が完全に無効になります。第二に、反復ではなく再帰を意味していると思います。

考慮事項: 配列をコピーする代わりに、一連のインデックスを配列に渡すことで同じ結果を得る方法を考えてください (開始と終了など)。

実際の質問に関しては、再帰を通じてブール値を返す方法。再帰関数から値を返すことについてのことは、各反復が値を渡さなければならないということです。これは一連の責任委任のようなものと考えることができます。最初の呼び出しは、会社の長のようなものです。彼はすべての作業を行うわけではないので、アシスタントに委任しますが、最初に 1 つの作業を行います。次に、アシスタントにはアシスタントなどがあります。カメはずっと下に;)

ただし、価値を取り戻すためには、チェーンの各人が前の人にそれを返さなければなりません。プログラミングに戻ると、これは検索を再帰的に呼び出すたびに、その値を返す必要があることを意味します。

最後に、これらを整理したら、基本ケースをより適切に定義する必要があります。(true) が true を返す場合、それがあなたがやろうとしていることだと思います。それ以外の場合は false を返します。ただし、H2CO3 で指摘されているように、これはあまり意味がありません。実際、前の if ステートメントif (n == 1) ...は、その後のコードが決して実行されないようにする必要があります。

于 2012-11-08T19:02:07.983 に答える
0

再帰検索の値を返す必要があります。

return search (value, new_array, m);

それ以外の場合は、検索を呼び出すときに、答えを捨てるだけです

于 2012-11-08T18:51:55.270 に答える
0

return search(...);メソッドを呼び出すだけでなく、呼び出す必要がありsearch()ます。そうしないと、戻り値がバブルアップされません。

さらに、このアルゴリズムはO(n)(配列のサイズで線形) であり、各反復で配列の半分をコピーするため、メモリ リークが発生し、非常に非効率的であることに注意してください。
実際には、要素の単純な線形検索よりもアルゴリズムが遅くなる可能性があります。

優れたバイナリ検索では、配列の半分をコピーする必要はありません。配列の半分を「見る」だけです。array+m配列として送信することで実現でき（上位半分）、n下位半分は減少するだけで十分です。

于 2012-11-08T18:52:12.057 に答える