Chapter 1
I
Introduction to algorithms
4
For example:
Here’s an example of how binary search works. I’m thinking of a
number between 1 and 100.
You have to try to guess my number in the fewest tries possible. With
every guess, I’ll tell
you if your guess is too low, too high, or correct.
Suppose you start guessing like this: 1, 2, 3, 4 …. Here’s how it would
go.
Looking for companies
in a phone book with
binary search
5
Binary search
This is
simple search (maybe
stupid search would be a better term). With
each guess, you’re eliminating only one number. If my number was 99,
it could take you 99 guesses to get there!
A better way to search
Here’s a better technique. Start with 50.
Too low, but you just eliminated
half the numbers! Now you know that
1–50 are all too low. Next guess: 75.
A bad approach to
number guessing
