Why is it (insertion_point - 1) returned by Collections.binarySearch when the item is not present and not inertion_point?

Question

The binarySearch method is used and wonders why - (insertion_point - 1) returned by Collections.binarySearch when the element is not present, and not the -point_instance? I understand why this is negative, but why -1?

Answer 1

Because you cannot have a negative 0.

Consider the situation if there was -1 . If the element was found with index 0, it will return 0. If the element was not found, but its insertion point was 0, it would also return zero. How could you distinguish between these two situations? With the addition of -1 , they now return 0 and -1 respectively, allowing you to distinguish.

And this -(insertion point) - 1 , slightly different from what your question says.

Answer 2

The documentation says:

Return

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 will be inserted into the list: the index of the first item larger than the key, or list.size() if all the items in the list are less than the specified key. Note that this ensures that the return value will be> = 0 if and only if the key is.

An important part is the last sentence:

Note that this ensures that the return value will be> = 0 if and only if the key is found.

If the effect is, you get two values ​​from binarySearch , combined in a smart way. You get information about whether an element is present (by the sign of the result) and where it belongs (value of the result).