A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Binary Search

You’ve probably played this guessing game as a child: I’m thinking of a number between 1 and 100. Keep guessing which number I’m thinking of, and I’ll let you know whether you need to guess higher or lower.

You may know intuitively how to play this game. You wouldn’t begin by guessing number 1. Instead, you’d probably 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 or 63. You’d keep on choosing the halfway mark in order ...