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.
}
key
, there is no guarantee which one will be found. This uncertainty renders it, basically, useless for most problems in competitive programming. $\endgroup$-(low+1)
can equivalently be written as~low
, perhaps making it clearer that it is a "safe" transformation (no ambiguous results) $\endgroup$