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

Question

I have tried all the answers from the related questions, like following:

Implement binary search using the `Collections.binarySearch` signature

Can't use binary search with Object Arraylist?

But none of them have worked for me.

The thing is that I want to do binarySearch() to find an object with a particular attribute in an ArrayList.

I am using the following code for this:

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



    }

}

Here search is the variable with the model that I want to search in the ArrayList vehicles.

I am getting the following error for this:

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

I am not able to use it, can anyone help me understand the cause and solution to the error.

Edit:

Sorry for not posting this before, sorting is not an issue. I have sorted the array list accordingly beforehand.

Answer 1

Collections#binarySearch searches a List for the same type of value that the list holds. Here, you're trying to search a list of vehicles with a string, and thus getting the error your shared.
One approach is to create a fake vehicle just so its model can be searched:

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

Note that in order to use binarySearch like that the list must be sorted according to the Comparator you provide (i.e., sorted according to the model in this case). If this assumption is not true, you'll have to use an O(n) search. E.g.:

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

Answer 2

Create a view of the list:

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

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

Then apply binary search to the view.

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

Note that whilst it would work using an anonymous class, like this, it would be better to define a named class (e.g. a nested class, or even a local class), in order that it can both extend AbstractList and implement RandomAccess, so that the binary search knows it can access efficiently by index.

Answer 3

Since this branch contains both correct solutions and it is both forbidden to use in my task, I will write my own, at the same time I will ask people to evaluate whether it is correct (the decision was made, tests passed)? If you looking for vehicles by model(String model):

int index = Collections.binarySearch(vehicles, model, new Comparator<Object>(){
        @Override
        public int compare(Object o1, Object o2) {
            Vehicle veh = (Vehicle)o1;
            String str = (String) o2;
            return veh.getModel().compareTo(str);
        }
    });

What do you think?