Does Arrays.BinarySearch require that the array is sorted in ascending order

ziggy picture ziggy · Jan 2, 2012 · Viewed 10k times · Source

According to the documentation:

public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)        

Searches the specified array for the specified object using the binary search algorithm.

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.

If it is not sorted, the results are undefined. If the array contains multiple elements equal to the specified object, there is no guarantee which one will be found.

Does the above mean that the Arrays.binarySearch method can only be used when the Array is sorted in ascending order?

I tested it as shown below

class Unturned {
    public static void main(String[] args) {
        String[] chars = {"a", "b", "c", "e","f","h","i"};
        MySort ms = new MySort();

        Arrays.sort(chars, ms);
        for(String c : chars ) System.out.print(c + " ");

        System.out.println("\n" + Arrays.binarySearch(chars, "d", ms));
    }
    static class MySort implements Comparator<String> {
        public int compare(String a, String b) {
            return b.compareTo(a);
} } }

output:

i h f e c b a
-5

-5 puts the insertion point at the element with value c which is correct. (i.e. -4-1).
Why is the documentation saying that the array must be sorted in ascending order?

Answer

Oliver Charlesworth picture Oliver Charlesworth · Jan 2, 2012

It says "must be sorted into ascending order according to the specified comparator". The part in bold is the crucial part; your array is indeed sorted according to the specified comparator (because you just sorted it!).