2
$\begingroup$

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.
}
$\endgroup$
4
  • $\begingroup$ Have you tried an example? It could help clarify things. $\endgroup$ Oct 4, 2021 at 5:41
  • $\begingroup$ By the way, the overflow bug mentioned in the article has been fixed in Java built-in library, java.util.arrays#binarysearch since ten years ago. $\endgroup$
    – John L.
    Oct 4, 2021 at 7:17
  • $\begingroup$ A side note. The bigger problem with Java's built-in binarysearch is if the array contains multiple elements with the specified key, there is no guarantee which one will be found. This uncertainty renders it, basically, useless for most problems in competitive programming. $\endgroup$
    – John L.
    Oct 4, 2021 at 7:21
  • 1
    $\begingroup$ -(low+1) can equivalently be written as ~low, perhaps making it clearer that it is a "safe" transformation (no ambiguous results) $\endgroup$
    – harold
    Oct 4, 2021 at 10:28

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.