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

Just to make it clearer - why the output is -1. Yes, you didn't sort it first is a big mistake. But here are some other things to take clear as well.

As @aioobe mentioned in his answer, but he didn't make it clear enough though I think. What does (-(insertion point) - 1) mean? Here is what the doc says.

The index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

So to make the answer more clear: -1 = -0 - 1

What I want to underline here is that the output maybe -2 or -3 or whatever. Because if all elements in the list are less than the specified key, the output will be -list.size() - 1.

Answer 2

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