Grokking Algorithms

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.

---