Commissioned for this museum · after John Mauchly, 1946
Binary Search
TypeScript·1946·28 lines·646 bytes
/**
* Binary search — halve the range until the answer is cornered.
*/
function search(sorted: number[], target: number): number {
let low = 0;
let high = sorted.length - 1;
while (low <= high) {
// Not (low + high) / 2. That sum can overflow a fixed-width integer,
// which is the bug that sat in the JDK for nine years.
const mid = low + Math.floor((high - low) / 2);
if (sorted[mid] === target) {
return mid;
}
if (sorted[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
const primes = [2, 3, 5, 7, 11, 13, 17, 19];
console.log(search(primes, 13));
console.log(search(primes, 4));Curator’s note
This one hangs here because it is famously hard to write correctly, which is an odd thing to say about twenty lines that halve a range.
Jon Bentley set it as an exercise to professional programmers and reported that around ninety per cent of them produced a version with a bug, given as much time as they wanted and no requirement to compile it. The first published description is from 1946; the first published version that was correct for all inputs did not arrive until 1962. And in 2006 Joshua Bloch found that the binary search in the Java standard library — read, reviewed and shipped for nine years — computed its midpoint as (low + high) / 2, which overflows to a negative number once the array is large enough. The fix is the line in this file.
Which raises something worth being honest about: JavaScript numbers are doubles, so that overflow cannot happen here, and the careful midpoint is strictly unnecessary in this language. It is written anyway. A museum can afford to exhibit the corrected form, and the correction is the historically interesting part — but if you copy this into JavaScript of your own, know that you are copying a habit rather than a fix.
The deeper reason it is hard has nothing to do with arithmetic. Every one of the classic bugs is an off-by-one at a boundary: < against <=, mid against mid + 1, whether the range is closed or half-open. The algorithm is trivial and the invariant is not, and the invariant is the thing being tested every time someone writes it from memory.