java - How does Collections.binarySearch work?

Question

I am trying to understand how Collections.binarySearch work in Java. I don't quite understand the output I get.

public static void main(String args[]) {
      // create arraylist       
      ArrayList<String>  arlst=new ArrayList<String> ();


      arlst.add("A");
      arlst.add("D");
      arlst.add("C");
      arlst.add("B");
      arlst.add("E");

      int index=Collections.binarySearch(arlst, "D", Collections.reverseOrder());     

      System.out.println(index);


   }    
}

The output of this code is -1.

And when the elements have been inserted at this order

      arlst.add("D");
      arlst.add("E");
      arlst.add("C");
      arlst.add("B");
      arlst.add("A");

I get 0 as a result. I thought the negative number was a result if the element was not found. Could anybody please clarify the output I receive?

Answer 1

Your data must be sorted according to the given comparator for the binary search to work as intended. (If it's not, the behavior is undefined.)

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

If the data is indeed sorted, the method will return the index of the sought element (if it's found) otherwise (-(insertion point) - 1), as specified in the documentation.

Example:

// Make sure it's sorted
Collections.sort(arlst, Collections.reverseOrder());

int index=Collections.binarySearch(arlst, "D", Collections.reverseOrder());     

System.out.println(index);  // prints 1