Why binary search is returning -1

Question

I am working on a small program:

public static void main( String args[])
    {
        String[] places = {"Bangalore","Pune","San Francisco","New York City"};
        Arrays.sort(places, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o2.compareTo(o1);
        }
    });
        System.out.println(Arrays.binarySearch(places, "New York City"));
    }

This program is printing -1, but I have "New York City" in my array then why the result is negative in this case?

Answer 1

Normally, Arrays.binarySearch assumes that the items in the array are already sorted in their natural order. The binary search algorithm doesn't work if it's not sorted this way.

Your Comparator is sorting the reverse of the natural order, so the algorithm can't find New York City.

But there is an overload of binarySearch that takes a Comparator, so that the algorithm can assume that it's sorted the same way that the Comparator defines the order.

The array must be sorted into ascending order according to the specified comparator (as by the sort(T[], Comparator) method) prior to making this call.

Reuse your Comparator in your binarySearch call.

String[] places = {"Bangalore","Pune","San Francisco","New York City"};

Comparator<String> c = new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        return o2.compareTo(o1);
    }
};
Arrays.sort(places, c);
System.out.println(Arrays.binarySearch(places, "New York City", c));

Then you'll get the correct output of 2.