Двоичный поиск по списку пар

Question

Мне нужно найти elem, который будет соответствовать element.
Моя программа работает, но она не эффективна. У меня очень большое ArrayList<Obj> pairs (более 4000 элементов), и я использую бинарный поиск, чтобы найти соответствующие индексы.

public int search(String element) { 
    ArrayList<String> list = new ArrayList<String>(); 
    for (int i = 0; i < pairs.size(); i++) { 
     list.add(pairs.get(i).getElem()); 
    } 
    return index = Collections.binarySearch(list, element); 
} 

Интересно, если есть более эффективный способ, чем с помощью цикла для копирования половины пара ArrayList в новый список ArrayList. Конструктор для Obj: Obj x = new Obj(String elem, String word);

Answer 1

Похоже, проблема решена. Как моя проблема была в том, что тип пары ArrayList был Obj и element Тип был String, я не мог использовать Collections.binarySearch, я решил создать новую переменную Obj x = new Obj(element, "");. Похоже, что строка не вызывает никаких проблем (она прошла мои тесты JUnit), так как мой метод compareTo сравнивает два elem s и игнорирует вторую переменную Obj x.

Мой обновленный метод:

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

Answer 2

Если ваш главный список (pairs) не изменится, то я бы рекомендовал создать TreeMap для поддержания обратного index структуру, например:

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++); 
} 

Теперь, при поиске элемента , все, что вам нужно сделать, это:

indexMap.get(element); 

это даст вам необходимую index или null, если элемент не е Xist. Кроме того, если элемент может присутствовать в списке несколько раз, тогда вы можете изменить indexMap на Map<String, List<Integer>>.

Вашего текущая итерация алгоритма список и вызывает бинарный поиск, поэтому сложность будет O(n) для итерации и O(log n) а TreeMap гарантирует log(n) время стоимость так будет гораздо быстрее.

Here документация от TreeMap.