Card 07/ 09
Reading a Negative Result From Java's binarySearch as Only Not Found
The negative number encodes where the key would be inserted.
When Java's Arrays.binarySearch does not find a key, it returns a negative number that encodes the insertion point, the index where the key would go to keep the array sorted: the result is -(insertion point) - 1. Code that reads any negative result as only "not found" throws that position away. This card shows the mistake, what it costs, and the one line that decodes the position. It matters whenever a sorted array grows by insertion, such as a sorted list of prices, scores or timestamps.
The symptom is an array that stops being sorted. Both listings below search 1 3 5 for 4 and then add it; the first appends it, and the second inserts it at the decoded position. Compare the last line each one printed.
import java.util.Arrays;
public class DiscardedResult {
public static void main(String[] args) {
int[] numbers = {1, 3, 5};
int result = Arrays.binarySearch(numbers, 4);
System.out.println("result: " + result);
if (result < 0) {
int[] grown = Arrays.copyOf(numbers, numbers.length + 1);
grown[numbers.length] = 4;
numbers = grown;
System.out.println("not found, appended");
}
System.out.println("array: " + Arrays.toString(numbers));
}
}result: -3
not found, appended
array: [1, 3, 5, 4]The second listing differs in one line: it turns the negative result back into a position before it grows the array.
import java.util.Arrays;
public class DecodedResult {
public static void main(String[] args) {
int[] numbers = {1, 3, 5};
int result = Arrays.binarySearch(numbers, 4);
System.out.println("result: " + result);
if (result < 0) {
int insertionPoint = -result - 1;
System.out.println("insertion point: " + insertionPoint);
int[] grown = new int[numbers.length + 1];
System.arraycopy(numbers, 0, grown, 0, insertionPoint);
grown[insertionPoint] = 4;
System.arraycopy(numbers, insertionPoint, grown, insertionPoint + 1, numbers.length - insertionPoint);
numbers = grown;
}
System.out.println("array: " + Arrays.toString(numbers));
}
}result: -3
insertion point: 2
array: [1, 3, 4, 5]Both runs got -3. The search ended with its lower index on 2, where 4 belongs between 3 and 5, and returned -(2) - 1. The extra -1 is there because an insertion point can be 0, and -0 would be indistinguishable from finding the key at index 0; subtracting 1 makes every miss strictly negative. So -result - 1, or ~result, which is the same value, recovers 2.
The cost of discarding it is quiet: the first listing left 1 3 5 4, and every later binary search on that array can now return wrong answers, with no exception to say so. Searching again to find the position would cost a second O(log n) search for something the first already computed.
The remedy is to decode the result whenever it is negative, as the second listing does. Python avoids the encoding altogether: bisect.bisect_left returns the insertion point directly, and bisect.insort inserts at it.
← → move through sections and cards