ペアのリストのバイナリ検索

Question

elementと一致するelemが必要です。
私のプログラムは動作しますが、効率的ではありません。私は非常に大きいArrayList<Obj> pairs（4000以上の要素）を持っており、私は一致するインデックスを見つけるためにバイナリ検索を使います。

ループを使用してArrayListペアの半分を新しいArrayListリストにコピーするより効率的な方法があるのだろうかと思います。 OBJのための コンストラクタ：Obj x = new Obj(String elem, String word);

Answer 1

問題が解決したようです。 ArrayListのペアの型がObjで、elementの型がStringだったため、Collections.binarySearchを使用できませんでした。新しい変数 Obj x = new Obj(element, "");を作成することにしました。私のcompareToメソッドが2つのelemを比較し、Obj xの第2の変数を無視するので、文字列が問題を引き起こさない（JUnitテストに合格した）ようです。

私の更新方法：

public int search(String element) { 
    Obj x = new Obj(element, ""); 
    int index = Collections.binarySearch(pairs, x); 

Answer 2

あなたのマスターリスト（pairs）が、その後変更されない場合は、私は、例えばindex構造、逆維持するためにTreeMapを作成お勧めします：要素を検索しながら、

List<String> pairs = new ArrayList<String>(); //list containing 4000 entries 

Map<String, Integer> indexMap = new TreeMap<>(); 

int index = 0; 
for(String element : pairs){ 
    indexMap.put(element, index++); 
} 

今を、すべてを行う必要がある：

要素が電子しない場合は、あなたに必要な indexまたは nullを与える

indexMap.get(element); 

xist。また、要素がリストに複数回存在する場合は、indexMapをMap<String, List<Integer>>に変更することができます。

あなたの現在のアルゴリズムが繰り返さリストとバイナリ検索を呼び出し、それははるかに高速になりますので、複雑さが反復してO(log n)TreeMapに対し保証log(n)時間コストのためにO(n)だろう。

HereのドキュメントTreeMapです。