Chapter 1
I
Introduction to algorithms
6
Too high, but again you cut down half the remaining numbers!
With
binary search, you guess the middle number and eliminate half the
remaining numbers every time
. Next is 63 (halfway between 50 and 75).
This is binary search. You just learned your first algorithm! Here’s how
many numbers you can eliminate every time.
Whatever number I’m thinking of, you can guess in a maximum of
seven guesses—because you eliminate so many numbers with every
guess!
Suppose you’re looking for a word in the dictionary. The dictionary has
240,000 words.
In the worst case
, how many steps do you think each
search will take?
Simple search could take 240,000 steps if the word you’re looking for is
the very last one in the book. With each step of binary search, you cut
the number of words in half until you’re left with only one word.
Eliminate half the
numbers every time
with binary search.
7
Binary search
Logarithms
You may not remember what logarithms are, but you probably know what
exponentials are. log
10
100 is like asking, “How many 10s do we multiply
together to get 100?” The answer is 2: 10 × 10. So log
10
100 = 2. Logs are the
flip of exponentials.
Logs are the flip of exponentials.
In this book, when I talk about running time in Big O notation (explained
a little later), log always means log
2
. When you search for an element using
simple search, in the worst case you might have to look at every single
element. So for a list of 8 numbers, you’d have to check 8 numbers at most.
For binary search, you have to check log
n
elements in the worst case. For
a list of 8 elements, log 8 == 3, because 2
3
== 8. So for a list of 8 numbers,
you would have to check 3 numbers at most. For a list of 1,024 elements,
log 1,024 = 10, because 2
10
== 1,024. So for a list of 1,024 numbers, you’d
have to check 10 numbers at most.
Note
I’ll talk about log time a lot in this book, so you should understand the con-
cept of logarithms. If you don’t, Khan Academy (khanacademy.org) has a
nice video that makes it clear.
So binary search will take 18 steps—a big difference! In general, for any
list of
n
, binary search will take log
2
n
steps to run in the worst case,
whereas simple search will take
n
steps.
|