What you need to know
You’ll need to know basic algebra before starting this book. In parti-
cular, take this function: f(
x
) =
x
× 2. What is f(5)? If you answered 10,
you’re set.
Additionally, this chapter (and this book) will be easier to follow if
you’re familiar with one programming language. All the examples in
this book are in Python. If you don’t know any programming languages
and want to learn one, choose Python—it’s great for beginners. If you
know another language, like Ruby, you’ll be fine.
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
|