Binary Search return value

Question

Google has the article Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Which primarily discusses the overflow on the mid calculation. However, what I found interesting was the return value for when key is not found. Initially, I thought the negative indicates the value was not found and low indicates where it should be inserted into the array. However, what is the +1 in return -(low+1); doing?

public static int binarySearch(int[] a, int key) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        int midVal = a[mid];
        
        if (midVal < key)
            low = mid + 1
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

Answer 1

There are multiple ways to handle the case when the key(the searched value) is not found by a binary search. Or any search on elements accessible by indices.

What you see is the Java approach, the approach that has been written by the foremost writer of Java built-in Libraries (also the author of the article in the question) and, henceforth, used by millions of Java developers around the world for about 20 years.

Here is Java official documentation for the method java.util.Arrays#binarysearch(int[] a, int key).

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.

That is, the method guarantees that the return value will not be a valid index if and only if the key is not found. This guarantee makes sure the return value is not usable when the key is not found, preventing wrong usage or failing faster.

If key is not found and low is 0 right before the method returns, the method should not return -low, since it is 0, which is a valid index. So, it returns -(low + 1), which is -1, an invalid index.

By the way, to find the insertion point when the key is not found, i.e., when returned_value < 0, we can use -returned_value - 1.