Search code examples
javastringoopscjp

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


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?


Solution

  • Each comparator defines an ordering on the elements of the given type. The requirement is merely that the array elements have to be sorted such that a[0] < ... < a[n-1] for some valid definition of <. That definition does not have to correspond to our conventional notion of < for e.g. numbers -- indeed, it could even be defined as being the conventional >.