リストがソートされているときにリスト内の値を見つける最良の方法

私はソートされたJava ArrayListを持っているとしましょう。今、私は値xのインデックスを探したいと思います。これを行うには、最速の方法（30行以上のコードなし）がありますか？ IndexOf（）メソッドの使用？単純なforループのすべての値を繰り返し処理しますか？いくつかのクールなアルゴリズムの使用？ 50個の整数キーを考えてみましょう。リストがソートされているときにリスト内の値を見つける最良の方法

出典

2009-05-23 Baversjo

Binary searchですが、50アイテムしかないので、誰が気にしますか（何百万回もしなければならない場合を除きます）。単純な線形検索は簡単で、50項目のパフォーマンスの差はごくわずかです。

を編集する：組み込みのjava.util.Collections binarySearchメソッドを使用することもできます。項目が見つからない場合でも挿入ポイントが返されることに注意してください。アイテムが実際にあなたが望むものであることを確認するために、余分な数のチェックをする必要があります。ポインタのための@Matthewに感謝します。

出典

2009-05-23 13:40:36 tvanfosson

50個のキーについて、私は完全に同意するものとします。開発者の時間は最近のCPU時間よりも重要です。 IndexOf（）を使用し、あなたの方法であります。 –

Java/has/this機能を除いて。 –

バイナリ検索は道のりです。リストには現在50項目しかないかもしれないが、コードが1年か2年で扱うべきことが分かっている。 –

tvanfossonが正しいとすれば、いずれかの時間が非常に短くなるため、このコードが頻繁に実行されない限り、大きな違いはありません。

しかし、Javaには、リスト（ArrayListsを含む）、バイナリ検索のための組み込み機能があります（Collections.binarySearch）。

出典

2009-05-23 13:51:16

キーが受け入れ可能な分布の場合、Interpolation Searchは実行時間を考慮すると非常に高速です。

コーディング時間を考慮すると、あなたのデータ型（私はC＃から来て、Javaを知らない人）のためにavailiableであればバイナリ検索で組み込むことができます。

出典

2009-05-23 13:53:32

import java.util.ArrayList; 
import java.util.Collections; 

ArrayList myList = new ArrayList(); 
// ...fill with values 

Collections.sort(myList); 
int index = Collections.binarySearch(myList, "searchVal");

編集：未テストコード

出典

2009-05-23 14:02:09

コードありがとうございました:) – Baversjo

リストがソートされているときにリスト内の値を見つける最良の方法

答えて

関連する問題