0

だから私は巨大な障害物にぶつかっています....多分それは私の論理がそこにないからかもしれませんが、私は自分でこれを理解することができないようです.

BinarySearch2つのインデックスを取得するように変更しようとしています。

最初のインデックスは、指定された数値 x の左端のインデックスと右端のインデックスです。数値が存在しない場合は、[-1,-1] が生成されます。

いずれかの方法。BinarySearch を変更しようとしていますが、うまくいかないようです。任意のポインタをいただければ幸いです。

public static Pair BinarySearchDup(int[] A, int x, int low, int high){
    int mid = (low + high) / 2;
    int left = -1, right = -1;
    while(low <= high){
        mid = (low + high) / 2;
        if(A[mid] == x){
            int newMid = mid;
            //check left
            if(left == -1){
                left = mid;
                return BinarySearchDup(A, x, low, mid - 1);
            }
            else if(right == -1){
                right = mid;
                return BinarySearchDup(A, x, newMid + 1, high);
            }       
            return new Pair(left, right);
        }
        else if(A[mid] < x)
            return BinarySearchDup(A, x, mid + 1, high);
        else// (A[mid] > x)
            return BinarySearchDup(A, x, low, mid - 1);
    }
    //if there are no matches of the number then it returns -1
    return new Pair(-1, -1);
}
4

2 に答える 2

0

私はあなたの考えを理解しているかどうかわかりませんが、それがうまくいかない理由は次のとおりです。

あなたのコードは以下と同等です:

public static Pair BinarySearchDup(int[] A, int x, int low, int high){
    int mid = (low + high) / 2;
    if(low <= high){        
        if(A[mid] == x)
            return BinarySearchDup(A, x, low, mid - 1);
        else if(A[mid] < x)
            return BinarySearchDup(A, x, mid + 1, high);
        else// (A[mid] > x)
            return BinarySearchDup(A, x, low, mid - 1);
    }

    return new Pair(-1, -1);        
}

実際、while ループに入ると常に戻るので、反復は 1 回しかありません。また、mid の値が x の場合、left は -1 であるため、常にこの if 句を入力します。または、while ループに入らない場合は、(-1, -1) を返します。お役に立てれば。

編集:通常のバイナリ検索を使用して、範囲全体を取得するまで、見つかったインデックスを行ったり来たりすることはできませんか?

于 2013-04-08T01:51:12.717 に答える
0

この問題を解決するために：

2 つのインデックスを取得するように BinarySearch を変更しようとしています。最初のインデックスは、指定された数値 x の左端のインデックスと右端のインデックスです。数値が存在しない場合は、[-1,-1] が生成されます。

私はこれを行います：

1) 二分探索を行います。ただし、ターゲットを一致と見なしてすぐに終了するのではなく、ターゲットよりも大きいと見なします (たとえば、ターゲットの左側を検索します)。この検索が終了すると、それは target の一番左のインスタンス、1 つ左 (コーディング方法に応じて - この場合は 1 つの右をチェックするだけ) になるか、存在しないことが確認されます。

2) 1) のようにバイナリ検索を実行しますが、ターゲットがターゲットよりも小さいことを考慮してください。これは、同様の方法で、ターゲットの最も右のインスタンスを見つけます。

これにより、O(logN) の複雑さが得られます。Petar Ivanov の「通常のバイナリ検索を使用して、範囲全体を取得するまで、見つかったインデックスを行ったり来たりできないでしょうか?」というアイデア。配列に膨大な数の重複がある場合、O(N) と同じくらい悪い可能性があります。ただし、予想される重複数 (または予想される配列サイズ) が小さい場合、変更されたロジックで二分探索を作り直す必要がないため、Petar Ivanov のアイデアはコーディングがはるかに簡単になります。

于 2013-04-08T03:25:23.163 に答える