oct 20, 2023algorithms3 min

guess my number

binary search, from a guessing game to a phonebook: why 100 numbers take 7 guesses and 4 billion take 32, why the list has to be sorted, and the bug that sat in Java's version for nine years.

I'm thinking of a number between 1 and 100. you guess, and I tell you higher or lower.

you could start at 1 and count up. if my number is 99, that's 99 guesses. that's a linear search: in the worst case, as many guesses as there are numbers.

or you guess 50. whatever I answer, half the numbers are gone. then 25 or 75, and half of what's left is gone. every guess cuts what's left in half, and 100 numbers can only be halved 7 times before one is left.

that's binary search. it's how you'd look up a name in a phonebook: open it in the middle, see if you went too far, and throw away the half it can't be in.

#it has to be sorted

"higher or lower" only means something if the list is in order. a phonebook in random order gives you nothing to throw away, and you're back to reading every page. binary search needs a sorted list, so it pays off when you sort once and search many times.

#in code

keep two marks around the part of the list where the item can still be, left and right. look at the one in the middle: if it's too small, move left past it. too big, move right before it.

function binarySearch(list, item) {
  let left = 0;
  let right = list.length - 1;
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (list[mid] === item) return mid;
    if (list[mid] < item) left = mid + 1;
    else right = mid - 1;
  }
 
  return -1;
}
 
binarySearch([2, 5, 8, 12, 16, 23, 38, 42, 56, 61, 72, 77, 84, 91, 95, 99], 61); // 9

#how many guesses

the most guesses you'll need is how many times the list can be halved: log₂ of its length, rounded up.

items	linear search, worst case	binary search, worst case
100	100	7
1,000,000	1,000,000	20
4,000,000,000	4,000,000,000	32

going from 100 items to 4 billion costs 25 more guesses.

#the bug in the textbook

it's ten lines, and it still took the industry a while to get right. in 2006, Joshua Bloch wrote that the binary search he'd written for Java's java.util.Arrays had a bug that sat there for about nine years, and so did the one in Jon Bentley's Programming Pearls. it's the middle line: in Java, (low + high) / 2 overflows once the sum passes the biggest int, which happens with arrays of about a billion items. the sum goes negative, and so does the index.

in JavaScript, numbers are 64-bit floats, so the sum of two indexes fits easily, even in the longest array JavaScript allows. in Java, the fix is low + (high - low) / 2.