# guess my number

2023-10-20 · 3 min read · #algorithms

Source: https://jopcmelo.com/writing/guess-my-number

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.

*(sketch: 100, 50, 25, 13, 7, 4, 2, 1, each halving drawn as an arc: 7 guesses)*

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.

*(sketch: sixteen sorted numbers. two brackets mark where 61 can still be, and a pointer marks the middle. 42 is too small, so the left bracket jumps past it. 77 is too big, so the right bracket moves in. the middle is now 61, and it gets circled. then it starts over)*

```javascript
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](https://research.google/blog/extra-extra-read-all-about-it-nearly-all-binary-searches-and-mergesorts-are-broken/) 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`.