0 
% java BinarySearch 1.txt < 2.txt

2 つのテキスト ファイル (1.txt と 2.txt) があり、2.txt には 1.txt にない値が含まれている場合、これらの値を得るためにバイナリ検索はどのように機能しますか? への引数BinarySearchがキーとソートされた配列である場合、これがどのように適用されるかわかりません。

二分探索のコードは次のとおりです。

import java.util.Arrays;

public class BinarySearch {

    // precondition: array a[] is sorted
    public static int rank(int key, int[] a) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            // Key is in a[lo..hi] or not present.
            int mid = lo + (hi - lo) / 2;
            if      (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else return mid;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] whitelist = In.readInts(args[0]);

        Arrays.sort(whitelist);

        // read key; print if not in whitelist
        while (!StdIn.isEmpty()) {
            int key = StdIn.readInt();
            if (rank(key, whitelist) == -1)
                StdOut.println(key);
        }
    }
}

ウィキペディアによると、私が理解したことから、バイナリ検索または半間隔検索アルゴリズムは、ソートされた配列内の指定された値 (入力「キー」) の位置を見つけます。

では、2 つのテキスト ファイルで珍しい値を見つけるにはどうすればよいのでしょうか。

4

3 に答える 3

0

私が質問を理解しているので、2.txtのエントリが1.txtにないことを（正しく）判断したときに、このプログラムがどのように機能するかを知りたいと思います。それは非常に簡単な答えです。

このアルゴリズムは、アレイのホワイトリストを並べ替えます。これは、要素0を指すようにloポインターを初期化し、ホワイトリストの最後の要素である要素whitelist.length-1を指すようにhiポインターを初期化します。配列セグメントは、最初の反復の配列全体です。これを機能させるには、配列を順序付けまたはソートする必要があります。

連続する反復ごとに、値が現在の配列セグメントの中央に見つからない場合、ロジックは、値が中央より上の半分のセグメントにある必要があるか、中央より下の半分のセグメントにある必要があるかを決定します。古い中間要素を除くそのハーフセグメントは、次の反復の新しい検索セグメントになります。アルゴリズムは、hiポインターとloポインターを調整して、一度に配列の残りのセグメントの半分に近づきます。配列内にある場合は、検索された値が存在する必要があります。

最終的に、配列にない検索値の場合、hiとlo（したがってmid）は同じ単一の要素に収束し、検索された配列の最後のセグメント、つまり1つの要素のみのセグメントになります。その要素に検索値がない場合、検索値とその要素の値に応じて、hiはmid-1になるか、loはmid + 1になります。いずれにしても、lo <であるため、while継続条件はfalseになります。 =hiはもう真ではありません。新しい残りの検索セグメントのサイズは負になりました。これは、whileが終了する前にリターンが発生しなかった場合、検索で前のセグメントの値が見つからず、検索するセグメントが残っていないことを意味すると解釈できます。したがって、検索値を配列に含めることはできません。

この質問で与えられた実装は機能します。ここで使用されているInクラスとStdInクラスを含むPrinceton.edustdlibを使用してテストしました。stdinパイプを使用してコマンドラインからコンパイルして実行し、2番目のテキストファイルをパイプします。おそらくクラスやいくつかのテクニックを調べるためのバイナリ検索メソッドのデモンストレーションを除いて、このアプリケーションをこのように実装することはないと思います。

ここに、二分探索が使用される理由に関するいくつかのさらなる背景があります。二分探索を使用する理由は、平均1.5 * logBase2（n）の複雑さで最悪の場合の2 * logBase2（n）の実行の複雑さを取得するためです。配列にない値の二分探索は、常に2 * logBase2（n）比較の最悪のケースになります。

バイナリ検索は、配列の一方の端から開始し、一致するものが見つかるか配列の最後に到達するまですべての要素を検索する線形検索よりもはるかに優れています。配列内の値の分布に応じて、平均検索は約n/2になる可能性があります。配列にない値の線形検索では、常に最悪の場合のn回の比較が行われます。

二分探索では、比較の各ペアは、可能性の半分を排除します。1024エントリの配列は、最大20回の比較で検索できます。線形探索の最大1024と比較してください。検索された配列のサイズを2乗すると、バイナリ検索の比較の数が2倍になります。二分探索では、1,048,576エントリの配列を検索でき、最大40回の比較が可能です。これを最大1,048,576の線形探索と比較してください。

質問で与えられた基本的なバイナリ検索アルゴリズムは、ソートまたは順序付けされたコレクションから継承するオブジェクトで非常に役立ち、継承されたメソッドをオーバーロードするために独自の比較および検索メソッドを実装する必要があります。オブジェクト間でより少ない、より多い、等しいと判断する比較があり、コレクションがその比較に従って順序付けまたはソートされている限り、この基本的なバイナリ検索アルゴリズムを使用してコレクションを検索できます。

于 2012-07-30T09:34:15.370 に答える
0

ハッシュテーブルを作成することは、intのみを含む大きなファイルを比較するための修正されたマージソートアルゴリズムよりも優れていると思います。テーブル。main のループが実行している次のファイルを一度に 1 int ずつ読み取り、int のハッシュを計算し、ハッシュに対応するハッシュ テーブルにテーブルに値が含まれているかどうかを比較します。私は完全なハッシュテーブルを想定しているので、衝突が発生した場合に変更する必要があるかもしれません.

于 2012-07-10T07:46:29.937 に答える
0 
while (!StdIn.isEmpty()) { //WHILE THE INPUT FILE (OR STANDARD INPUT) ISN'T EMPTY
            int key = StdIn.readInt();  //GET THE NEXT INTEGER
            if (rank(key, whitelist) == -1) // USE BINARY SEARCH TO SEARCH FOR THAT INTEGER
                StdOut.println(key); //PRINT WHEN IT'S NOT FOUND
        }

N バイナリ検索を実行しているコード (N は標準入力ファイル内の整数の数)。複雑さは O(n * log n) + O(m * log n) です。n と m は異なるファイルのサイズです。while リストの n とその他の m です。これは、whilelist が他のファイルよりもはるかに小さい場合にうまく機能します。そうでない場合は、両方のファイルをソートし、マージソートのマージステップなどを使用してそれらを比較することをお勧めします。

于 2012-07-10T05:53:26.587 に答える