バイナリ検索が

Question

イム おかげ

Answer 1

アルゴリズムがあるべき注文のArrayList内のバイナリ検索としてではなく順序付けられたリストのために同じように動作するJavaのコードを実装する方法を探してArrayListとListの両方で同じですが、どちらも注文されています。

Answer 2

リストが注文されていない場合は、バイナリ検索を実行できないことにも注意してください。それは意味をなさない。バイナリ検索は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の実装を使用したい場合はWikipedia

を、次に使用します。

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

アレイをaもちろん並べ替えが必要です。

Answer 3

「バイナリ検索」は、リストの要素（または要素への何らかのポインタ）がメモリ内に順番に整理されている場合にのみ意味があり、検索が「低」と「高」の索引に絞り込まれている場合、他のすべての要素をスローする必要なく、（Low + High）/ 2の位置に素早くジャンプすることができます。これは、一般的なリスト（リンクされたリストの場合があります）では機能しません。そのようなものについては、リストの先頭からすべての要素を順番に調べるよりも、実際にはうまくいくわけではありません。

Answer 4

あなたはどのList上のバイナリ検索に

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

を使用することができます。それはArrayListとLinkedListと他のListで動作します。この方法は、ログ（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");