Search code examples
javacomparatorbinary-search

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


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.


Solution

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