8

順序付けられたArrayListでのバイナリ検索と同じように機能するコードをJavaで実装する方法を探していますが、順序付けられたリストのおかげで

4

4 に答える 4

23

使用できます

Collections.<T>binarySearch(List<T> list, T key)

任意のバイナリ検索用List。それArrayListはLinkedList何度も何度も他のList.

でも：

二分探索は、各要素に直接アクセスできる場合にのみ高速です。

このメソッドは、「ランダム アクセス」リスト (ほぼ一定時間の位置アクセスを提供する) に対して log(n) 時間で実行されます。指定されたリストが RandomAccess インターフェイスを実装しておらず、大きい場合、このメソッドは、O(n) リンク トラバーサルと O(log n) 要素比較を実行するイテレータ ベースのバイナリ検索を実行します。

List「ランダムアクセス」を提供しない場合はList、これを提供するコピーを作成することで運が良くなる可能性があります。

LinkedList<String> list = new LinkedList<String>();
// fill

どちらでもいい

ArrayList<String> fastList = new ArrayList<String>(list);
Collections.binarySearch(fastList, "Hello World");

または多分そう

String[] array = list.toArray(new String[list.size()]);
Arrays.binarySearch(array, "Hello World");

Listデフォルトで順序付けされておらず、検索する前にソートする必要がある場合は、配列を使用してソートすることで最良の結果が得られる可能性があります。

Collections.sort(list);

ソートされてリストを再作成するために使用される一時的な配列を作成します。これは、配列で直接行う場合に防ぐことができます。

String[] array = list.toArray(new String[list.size()]);
Arrays.sort(array);
Arrays.binarySearch(array, "Hello World");
于 2013-08-07T18:38:28.973 に答える
1

「バイナリ検索」は、リストの要素 (または要素へのある種のポインター) がメモリ内で順番に編成されている場合にのみ意味があります。そのため、検索がインデックス Low と High に絞り込まれていることがわかっている場合は、右にジャンプできます。 (低 + 高) / 2 の要素に、他のすべての要素をゆっくりと通過する必要はありません。これは、LinkedList である可能性がある一般的なリストでは機能しません。そのような場合、リストの先頭から始めて、すべての要素を順番に見ていくよりもうまくいくことはありません。

于 2013-08-07T18:15:32.287 に答える
1

ArrayListanと aListはどちらも順序付けられているため、アルゴリズムは同じでなければなりません。

于 2013-08-07T18:13:55.177 に答える
-1

また、リストが順序付けられていないと、バイナリ検索を実行できないことも覚えておく必要があります。意味がありません。二分探索はO(log n)、リストが順序付けられていることを知っているため、リストの半分をいつでも無視できるためです。リストが順序付けられていない場合、検索は O(n) になり、バイナリは使用できません。

二分探索の独自の実装は次のようになります。

int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin)
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = midpoint(imin, imax);

      // three-way comparison
      if (A[imid] > key)
        // key is in lower subset
        return binary_search(A, key, imin, imid-1);
      else if (A[imid] < key)
        // key is in upper subset
        return binary_search(A, key, imid+1, imax);
      else
        // key has been found
        return imid;
    }
}

ソース:ウィキペディア

Java.util 実装を使用する場合は、次を使用します。

java.util.Arrays.binarySearch(int[] a, int key)

もちろん、配列aはソートする必要があります。

于 2013-08-07T18:14:57.733 に答える