如何使用 `Collections.binarySearch()` 通过对象的 ArrayList 进行二进制搜索？

Question

我已经尝试了相关问题的所有答案，如下所示：

Can't use binary search with Object Arraylist?

但是 none 对我有用。

问题是我想 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是我要在ArrayListvehicles.

中搜索的model的变量

我收到以下错误：

The method binarySearch(List, T, Comparator) in the type Collections is not applicable for the arguments (ArrayList, String, Comparator)

我无法使用它，任何人都可以帮助我了解错误的原因和解决方法。

编辑：

很抱歉之前没有发布这个，排序不是问题。我事先已经对数组列表进行了相应的排序。

Answer 1

Collections#binarySearch 在 List 中搜索列表中包含的相同类型的值。在这里，您尝试使用字符串搜索车辆列表，从而得到您共享的错误。
一种方法是制造一辆假车，这样它的模型就可以被搜索到：

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

请注意，为了像这样使用 binarySearch，列表必须根据您提供的 Comparator 进行排序（即，在本例中根据模型进行排序）。如果这个假设不成立，则您必须使用 O(n) 搜索。例如：

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

Answer 2

创建列表视图：

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

请注意，虽然它可以像这样使用匿名 class，但最好定义一个命名的 class（例如嵌套的 class，甚至是本地的class)，以便它既可以extend AbstractList又可以implement RandomAccess，这样二分查找就知道它可以通过索引高效地访问。

如何使用 `Collections.binarySearch()` 通过对象的 ArrayList 进行二进制搜索？

How to use `Collections.binarySearch()` to do a binary search though an ArrayList of objects?

java

binary-search

comparator