Strange output for Binary Search when result is not found

I am getting a strange output when the result is not found.

import java.util.Arrays; import java.util.Comparator; public class BinarySearch { public static void main(String args[]) { String arr[] = { "c", "a", "e", "f", "z" }; MySort ms = new MySort(); Arrays.sort(arr, ms); for (String c : arr) { System.out.println(c); } System.out.println(Arrays.binarySearch(arr, "b", ms)); } static class MySort implements Comparator<String> { @Override public int compare(String o1, String o2) { return o2.compareTo(o1); } } } 

Output: z f e c a -6

Why does it print -2 when i pass "y" as my query param and -5 when i pass b. Can anyone let me know what is happening if the result is not found.

2 Answers

I don't know Java well, but Google gave me this link.

If the search fails, the return value indicates the insertion point - the index where you could insert your search item and it preserves the sorted order. So you can distinguish it from successful results, the insertion point value is always negative.

The actual return value is -(insertpoint) - 1. If you know your twos-complement (binary representation of signed integers) you'll recognise this as the bitwise not of the insert point. This value is slightly interesting because every possible non-negative integer of any particular bit-width has a negative bitwise-complement (flip all bits, including the sign bit).

Arrays#binarySearch() returns the index of the element you are searching, or if it is not found, then it returns the (-index - 1) where index is the position where the element would be inserted in the sorted array.

From docs:

Returns:
index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array 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.

Now, with your array sorted, "b" would be inserted at index = 1, right after "a". And hence the return value is (-1 - 1) = -2