Как использовать `Collections.binarySearch ()` для выполнения бинарного поиска по ArrayList объектов?

Question

Я перепробовал все ответы на похожие вопросы, например:

Реализация бинарного поиска с использованием подписи `Collections.binarySearch`

Не можете использовать бинарный поиск с Object Arraylist?

Но ни один из них не работал для меня.

Дело в том, что я хочу сделать binarySearch(), чтобы найти объект с определенным атрибутом в ArrayList.

Я использую для этого следующий код:

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

public class SearchingThread extends Thread {

    private String search;
    private ArrayList<Vehicle> vehicles;

    public SearchingThread(String search, ArrayList<Vehicle> vehicles) {
        this.search = search;
        this.vehicles = vehicles;
    }

    public void run() {

        Comparator<Vehicle> comp = new Comparator<Vehicle>() {

            @Override
            public int compare(Vehicle o1, Vehicle o2) {
                return o1.getModel().compareTo(o2.getModel());
            }

        };

        int index = Collections.binarySearch(vehicles, search, comp);



    }

}

Здесь search - это переменная с model, которую я хочу найти в ArrayList vehicles.

Я получаю следующую ошибку:

Метод binarySearch (List, T, Comparator) в типе Collections не применим для аргументов (ArrayList, String, Comparator)

Я не могу его использовать, может кто-нибудь помочь мне понять причину и способ устранения ошибки.

Edit:

Извините, что не опубликовал это раньше, сортировка не является проблемой. Я заранее отсортировал список массивов.

Answer 1

Создать вид списка:

List<String> view = new AbstractList<String>() {
  @Override public int size() {
    return vehicles.size();
  }

  @Override public String get(int i) {
    return vehicles.get(i).getModel();
  }
};

Затем примените бинарный поиск к представлению.

int index = Collections.binarySearch(view, search);

Обратите внимание, что, хотя он будет работать с использованием анонимного класса, например, было бы лучше определить именованный класс (например, вложенный класс или даже локальный класс), чтобы он мог как extend AbstractList, так и implement RandomAccess, так что двоичный поиск знает, что он может получить эффективный доступ по индексу.

Answer 2

Collections#binarySearch ищет значение List того же типа, что и список. Здесь вы пытаетесь найти список автомобилей со строкой и, таким образом, получаете сообщение об ошибке.
Один из подходов состоит в том, чтобы создать поддельное транспортное средство, чтобы его модель можно было искать:

Vehicle modelDummy = new Vehicle();
modelDummy.setModel(search);
int index = Collections.binarySearch(vehicles, modelDummy, comp);

Обратите внимание, что для использования binarySearch подобным образом список должен быть отсортирован в соответствии с предоставленным вами Comparator (т.е. в данном случае отсортировано по модели). Если это предположение неверно, вы должны использовать поиск O (n). E.g.:

Vehicle vehicle = vehicles.stream().filter(v -> v.getModel().eqauls(search)).findFirst();