1 
int recurbinarysearch(int * oringalary, int low, int high, int target) {

    if (low > high) {
        return -1;
    } else {
        int mid = (low + high) / 2;
        if (target == * (oringalary + mid)) return mid;
        if (target > * (oringalary + mid)) return recurbinarysearch(oringalary, mid + 1, high, target);
        if (target < * (oringalary + mid)) return recurbinarysearch(oringalary, low, mid - 1, target);
    }
}

私の再帰的二分探索アルゴリズムにエラーが見られる人はいますか? 時折、正しくないインデックスを返します (ほとんどの場合、1 つずれています) が、たまにずれることがあります。通常、しかし、それは正しいです。問題がわかりません。助けていただければ幸いです。

4

2 に答える 2

1

二分探索の詳細については、Jon Bentley のProgramming Pearlsを参照してください。

これは、Programming Pearls に非常にインスパイアされた、コードのテスト ハーネスと、インストルメント化されたコードのバージョンです。私が行った唯一の変更は、バイナリ検索で (現在はコメントアウトされています) デバッグ印刷を追加することです。テスト コードからの出力はほぼ完璧です (ハーネスはすべて合格と表示していますが、完全には正しくありません)。

N =  0: 
search for  0 in  0 entries - returned  0 found  0 PASS
N =  1: [0] = 1;
search for  0 in  1 entries - returned -1          PASS
search for  1 in  1 entries - returned  0 found  1 PASS
search for  2 in  1 entries - returned -1          PASS
N =  2: [0] = 1;[1] = 3;
search for  0 in  2 entries - returned -1          PASS
search for  1 in  2 entries - returned  0 found  1 PASS
search for  2 in  2 entries - returned -1          PASS
search for  3 in  2 entries - returned  1 found  3 PASS
search for  4 in  2 entries - returned -1          PASS
N =  3: [0] = 1;[1] = 3;[2] = 5;
search for  0 in  3 entries - returned -1          PASS
search for  1 in  3 entries - returned  0 found  1 PASS
search for  2 in  3 entries - returned -1          PASS
search for  3 in  3 entries - returned  1 found  3 PASS
search for  4 in  3 entries - returned -1          PASS
search for  5 in  3 entries - returned  2 found  5 PASS
search for  6 in  3 entries - returned -1          PASS
N =  4: [0] = 1;[1] = 3;[2] = 5;[3] = 7;
search for  0 in  4 entries - returned -1          PASS
search for  1 in  4 entries - returned  0 found  1 PASS
search for  2 in  4 entries - returned -1          PASS
search for  3 in  4 entries - returned  1 found  3 PASS
search for  4 in  4 entries - returned -1          PASS
search for  5 in  4 entries - returned  2 found  5 PASS
search for  6 in  4 entries - returned -1          PASS
search for  7 in  4 entries - returned  3 found  7 PASS
search for  8 in  4 entries - returned -1          PASS
N =  5: [0] = 1;[1] = 3;[2] = 5;[3] = 7;[4] = 9;
search for  0 in  5 entries - returned -1          PASS
search for  1 in  5 entries - returned  0 found  1 PASS
search for  2 in  5 entries - returned -1          PASS
search for  3 in  5 entries - returned  1 found  3 PASS
search for  4 in  5 entries - returned -1          PASS
search for  5 in  5 entries - returned  2 found  5 PASS
search for  6 in  5 entries - returned -1          PASS
search for  7 in  5 entries - returned  3 found  7 PASS
search for  8 in  5 entries - returned -1          PASS
search for  9 in  5 entries - returned  4 found  9 PASS
search for 10 in  5 entries - returned -1          PASS
N =  6: [0] = 1;[1] = 3;[2] = 5;[3] = 7;[4] = 9;[5] = 11;
search for  0 in  6 entries - returned -1          PASS
search for  1 in  6 entries - returned  0 found  1 PASS
search for  2 in  6 entries - returned -1          PASS
search for  3 in  6 entries - returned  1 found  3 PASS
search for  4 in  6 entries - returned -1          PASS
search for  5 in  6 entries - returned  2 found  5 PASS
search for  6 in  6 entries - returned -1          PASS
search for  7 in  6 entries - returned  3 found  7 PASS
search for  8 in  6 entries - returned -1          PASS
search for  9 in  6 entries - returned  4 found  9 PASS
search for 10 in  6 entries - returned -1          PASS
search for 11 in  6 entries - returned  5 found 11 PASS
search for 12 in  6 entries - returned -1          PASS
N =  7: [0] = 1;[1] = 3;[2] = 5;[3] = 7;[4] = 9;[5] = 11;[6] = 13;
search for  0 in  7 entries - returned -1          PASS
search for  1 in  7 entries - returned  0 found  1 PASS
search for  2 in  7 entries - returned -1          PASS
search for  3 in  7 entries - returned  1 found  3 PASS
search for  4 in  7 entries - returned -1          PASS
search for  5 in  7 entries - returned  2 found  5 PASS
search for  6 in  7 entries - returned -1          PASS
search for  7 in  7 entries - returned  3 found  7 PASS
search for  8 in  7 entries - returned -1          PASS
search for  9 in  7 entries - returned  4 found  9 PASS
search for 10 in  7 entries - returned -1          PASS
search for 11 in  7 entries - returned  5 found 11 PASS
search for 12 in  7 entries - returned -1          PASS
search for 13 in  7 entries - returned  6 found 13 PASS
search for 14 in  7 entries - returned -1          PASS
N =  8: [0] = 1;[1] = 3;[2] = 5;[3] = 7;[4] = 9;[5] = 11;[6] = 13;[7] = 15;
search for  0 in  8 entries - returned -1          PASS
search for  1 in  8 entries - returned  0 found  1 PASS
search for  2 in  8 entries - returned -1          PASS
search for  3 in  8 entries - returned  1 found  3 PASS
search for  4 in  8 entries - returned -1          PASS
search for  5 in  8 entries - returned  2 found  5 PASS
search for  6 in  8 entries - returned -1          PASS
search for  7 in  8 entries - returned  3 found  7 PASS
search for  8 in  8 entries - returned -1          PASS
search for  9 in  8 entries - returned  4 found  9 PASS
search for 10 in  8 entries - returned -1          PASS
search for 11 in  8 entries - returned  5 found 11 PASS
search for 12 in  8 entries - returned -1          PASS
search for 13 in  8 entries - returned  6 found 13 PASS
search for 14 in  8 entries - returned -1          PASS
search for 15 in  8 entries - returned  7 found 15 PASS
search for 16 in  8 entries - returned -1          PASS
N =  9: [0] = 1;[1] = 3;[2] = 5;[3] = 7;[4] = 9;[5] = 11;[6] = 13;[7] = 15;[8] = 17;
search for  0 in  9 entries - returned -1          PASS
search for  1 in  9 entries - returned  0 found  1 PASS
search for  2 in  9 entries - returned -1          PASS
search for  3 in  9 entries - returned  1 found  3 PASS
search for  4 in  9 entries - returned -1          PASS
search for  5 in  9 entries - returned  2 found  5 PASS
search for  6 in  9 entries - returned -1          PASS
search for  7 in  9 entries - returned  3 found  7 PASS
search for  8 in  9 entries - returned -1          PASS
search for  9 in  9 entries - returned  4 found  9 PASS
search for 10 in  9 entries - returned -1          PASS
search for 11 in  9 entries - returned  5 found 11 PASS
search for 12 in  9 entries - returned -1          PASS
search for 13 in  9 entries - returned  6 found 13 PASS
search for 14 in  9 entries - returned -1          PASS
search for 15 in  9 entries - returned  7 found 15 PASS
search for 16 in  9 entries - returned -1          PASS
search for 17 in  9 entries - returned  8 found 17 PASS
search for 18 in  9 entries - returned -1          PASS

ほとんどすべて問題ありません。唯一の問題の子は最初の検索です。空の配列には値が見つからないため、これは失敗するはずです。

テストコードは次のとおりです。

#include <stdio.h>

int recurbinarysearch(int *oringalary, int low, int high, int target)
{
    //printf("-->> %d..%d: ", low, high);
    if (low > high)
    {
        //printf("<<-- %d ", -1);
        return -1;
    }
    else
    {
        int mid = (low + high) / 2;
        if (target == * (oringalary + mid))
        {
            //printf("<<-- %d ", mid);
            return mid;
        }
        if (target > * (oringalary + mid))
        {
            int r = recurbinarysearch(oringalary, mid + 1, high, target);
            //printf("<<-- %d ", r);
            return r;
        }
        if (target < * (oringalary + mid))
        {
            int r = recurbinarysearch(oringalary, low, mid - 1, target);
            //printf("<<-- %d ", r);
            return r;
        }
    }
}

int main(void)
{
    for (int i = 0; i < 10; i++)
    {
        int a[i+1]; // No zero-size arrays in C
        printf("N = %2d: ", i);
        for (int j = 0; j < i; j++)
        {
            a[j] = 2 * j + 1;
            printf("[%d] = %d;",j, a[j]);
        }
        putchar('\n');

        for (int j = 0; j < 2*i+1; j++)
        {
            int f = recurbinarysearch(a, 0, i, j);
            //putchar('\n');  // debug
            printf("search for %2d in %2d entries - returned %2d",
                    j, i, f);
            if (f >= 0 && f <= i)
            {
                printf(" found %2d", a[f]);
                printf(" %s", (a[f] == j) ? "PASS" : "FAIL");
            }
            else
                printf(" %8s %s", "", (j % 2 == 0) ? "PASS" : "FAIL");
            putchar('\n');
        }
    }
    return(0);
}

空の配列のケースを処理する方法については、あなたにお任せします。

于 2013-02-19T06:31:05.283 に答える
1

編集 これは受け入れられているので、本当に正しい答えに変えようとする必要があると思います。

私は当初、質問がハーフオープン境界を使用していると想定していました (以下の「注」以降を参照)。実際には（正しく）包括的境界を使用しています。最初の呼び出しで、low=0およびhigh=n-1.

包括的境界を使用することは、しばしば悪いことと見なされます。Dijkstra の古典的な記事 (PDF) を参照してください。C ファミリ言語では、ハーフ オープン境界が一般的な規則であり、for (i = 0; i < n; i++)overが優先されfor (i = 0; i <= n-1; i++)ます。ただし、包括的な境界が使用されていることを考えると、問題のコードは正しいようです。

ただし、コメントで WhozCraig が発見したように、呼び出し元のコードはその規則を尊重しておらず、間違った境界を渡していました。検索範囲に境界外のガベージ アイテムが含まれていました。その余分なアイテムはガベージであるため、範囲内のアイテムがソートされているという仮定も無効になる可能性があります。ほとんどの検索では、そのごみアイテムは見つかりません (ごみの価値があるものを検索する可能性は低いため) が、検索の方向を誤ってしまいます。

注 これはおそらく答えではありませんが、コメントするには長すぎます。

あなたの境界は包括的、排他的、または半分開いていますか?

で半開low、排他でを仮定しhighます。もしそうなら、この行は間違っているように見えます...

if (target < * (oringalary + mid))
    return recurbinarysearch(oringalary, low, mid - 1, target);

理由は、アイテムを で確認しましたが、新しい排他的上限としてmidを使用しているためです。これは、チェックされていない のアイテムが誤って検索から除外されたことを意味します。ラインは...mid - 1mid - 1

if (target < * (oringalary + mid))
    return recurbinarysearch(oringalary, low, mid, target);

これにより、アイテムmid - 1が検索範囲内に保持されます。mid上限が排他的であるため、のアイテムは再度検索されません。

二分探索で境界を台無しにすることは一般的な問題であり、見た目よりも多くのエラーが発生します。

ただし、これだけではあなたの症状を説明することはできません -時々 (おそらく検索の約 50%)アイテムを見つけられないはずですが、成功した検索の間違った位置を報告するべきではありません.

二分探索で境界が間違っている場合の通常の症状は、無限ループ (境界から除外されていないために同じ項目が繰り返しチェックされる) または存在する項目を検索で見つけられない (項目が検索範囲から除外されたため) です。チェックされていません）。

正直なところ、あなたの症状がどのように発生するのかわかりません。関数が終了する可能性のあるすべての方法で、正しい成功の結果が得られるか、-1失敗の結果が得られる必要があります。私が考えることができる唯一の例外は、このコードの外側にあります。たとえば、-1結果のチェックに失敗するなど、結果を誤って解釈することです。

ところで-これは、反復ごとに1回の比較のバイナリ検索について、私の質問と回答を売春婦に説明する絶好の機会です。

編集境界に別の問題を見つけたと思います-まだ半分開いていると仮定すると、この行は間違っています...

if (low > high) {

そしてあるべき...

if (low >= high) {

その理由は、半分開いた境界の場合、境界が等しい場合、その間にチェックする項目がないためです。上限がそれと等しく、排他的であるため、下限の項目でさえ有効ではありません。これにより、引き続きテストできます

于 2013-02-19T05:01:46.373 に答える