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.
