Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Collections.binarySearch(List list, K key) clarification. Java

Given the following statement, taken from this Oracle java tutorial, related to the binarySearch() method of the class Collections:

The return value is the same for both forms. If the List contains the search key, its index is returned. If not, the return value is (-(insertion point) - 1), where the insertion point is the point at which the value would be inserted into the List, or the index of the first element greater than the value or list.size() if all elements in the List are less than the specified value.

Why does the return value of binarySearch() not return only the negative index instead of the negative index minus 1? (the part in bold of the quote above mentioned).

In brief: why (-(insertion point) - 1) and not only (-(insertion point))?

Thanks in advance.

like image 498
Rollerball Avatar asked Apr 04 '13 12:04

Rollerball


2 Answers

That's because -(insertion point) would be ambiguous. You wouldn't be able to tell the following apart:

  • item found at position 0;
  • item not found, and insertion point is 0.

With -(insertion point) - 1, the above two cases result in different return values (0 and -1).

like image 116
NPE Avatar answered Sep 22 '22 18:09

NPE


from your link

This admittedly ugly formula guarantees that the return value will be >= 0 if and only if the search key is found. It's basically a hack to combine a boolean (found) and an integer (index) into a single int return value

like image 35
NimChimpsky Avatar answered Sep 21 '22 18:09

NimChimpsky