Why does the Collections.binarySearch(List<? extends T> list, T key, Comparator<? super T&g-CodePudding

Here is my code:

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

class MyComp implements Comparator<String> {

    @Override
    public int compare(String o1, String o2) {
        return o1.compareTo(o2);
    }
    
}
public class CollectionsAlgo2 {

    public static void main(String[] args) {
        // Create an ArrayList
        ArrayList<String> al = new ArrayList<>();
        
        // Add elements to the array list.
        al.add("C");
        al.add("A");
        al.add("E");
        al.add("B");
        al.add("D");
        al.add("F");
        al.add(1, "A2");
        
        System.out.println("al: " al);
        Collections.sort(al);
        System.out.println("al after sorting: " al);
        int pos = Collections.binarySearch(al, "B", new MyComp());
        System.out.println("pos: " pos);

    }

}

My question is what is the purpose of having a Comparator reference as parameter in the Collections.binarySearch(List<? extends T> list, T key, Comparator<? super T> c) as we are already passing the list sorted in ascending order?

How could this Comparator reference help in doing the binary search?

CodePudding user response：

Fundamentally, the binary search algorithm needs to know how to compare elements. When it examines a bisection point it needs to know if the element you're searching for is to the left or the right. That requires a comparison.

There are two binarySearch methods (1, 2). If your elements are Comparable then you don't need to pass a comparator. You can just pass the list and the search key:

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)

If they're not Comparable then you need to tell binarySearch how to compare them by passing a custom Comparator:

public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

In your example code, Strings are Comparable, so you don't need MyComp.

int pos = Collections.binarySearch(al, "B");

CodePudding user response：

Remember that there are many different methods on Java's array class in order to use Binary Search. You can find a list of them here.

In general, if you are searching for a primitive, byte, or comparable object in some array or list, you should be using one of the methods that doesn't include any comparator.

However, what if you have a list of objects that aren't comparable by default? For example, say you define a Person data type, which has some properties such as a height, and age, and a name. Now, say you are storing a list of persons. If you wanted to find a certain Person in a sorted list of Person objects, by default, Java has no idea how to perform this binary search. As a reminder, Java determines where to move in the binary search by comparing the key it is currently inspecting to the target key. But, Java has no idea what it means to check whether one Person object is greater, less than, or equal to another. Should it use the height to determine which is greater? Should it compare based on last name (or any other variable)? This is where comparators come in. I need to tell Java what it means when I ask to compare two Person objects.

To write the comparator, you need to create a class (this can be a private class in the same file as the object, or you can even write it in the method itself) which implements two methods: compare and equals. You can see the documentation here. Once you write this, you pass in the comparator you just created, so Java now knows how to compare the objects in the given list or array.