A Common-Sense Guide to Data Structures and Algorithms

Binary Search

You’ve probably played this guessing game when you were a child (or maybe you play it with your children now): I’m thinking of a number between 1 and 100. Keep on guessing which number I’m thinking of, and I’ll let you know whether you need to guess higher or lower.

You know intuitively how to play this game. You wouldn’t start the guessing by choosing the number 1. You’d start with 50 which is smack in the middle. Why? Because by selecting 50, no matter whether I tell you to guess higher or lower, you’ve automatically eliminated half the possible numbers!

If you guess 50 and I tell you to guess higher, you’d then pick 75, to eliminate half of the remaining numbers. If after guessing 75, I told you to guess lower, you’d pick 62 ...