# Invariant Binary Search

### Guessing game

Say we were playing a guessing game where I pick an integer between
1 and 100 and you guess it. For each guess, I tell you if its
greater than, less than, or equal to my number. How would you play
this so that you minimize the number of guesses? The naive approach
would be to start from 1 and go upto 100. The worst case here is
that if I picked the number 100, you would need 100 guesses. Is
there a way to improve?

### Binary Search

Say that my number was 43. Using the naive linear search, you would
need 43 guesses. However, the "smarter" way to play this game would be
to start halfway at 50. Then, I'll tell you that my number is less
than 50 so you effectively eliminate half of the possible guesses.
Repeating this process, the search sequence would look like this:

50, 25, 37, 43

For our first guess, we knew our number had to be between **1** and a **100** so we guess halfway at 50.

For the second guess, we know it is less than 50, so it is between **1**and **49** so we guess 25.

Third guess: lower bound = **26**, upper bound = **49** so we guess 37.

Fourth guess: lower bound = **38**, upper bound = **49**, guess = 43.