The Self-Taught Computer Scientist

nent. The process of exponentiation means raising 
b to the power n. For example, 2**2 = 2*2, 2**3 
= 2*2*2, and so on. A logarithm is the power you must raise a number to in order to produce another 
number. In other words, it is the inverse of exponentiation. For example, a logarithm can tell you how 
many times you need to multiply 2 by itself to get 8. That question in mathematical notation is log
2
(8). 
The solution to log
2
(8) is 3 because you need to multiply 2 by itself 3 times to get 8 (Figure 3.6).

---

Chapter 3 Search Algorithms
31
In a binary search, the first time you halve your list, you will have 
n/2 items left in it. After the 
second iteration, you will have 
n/2/2 items left, and after the third iteration, you will have n/2/2/2 items 
left. Put another way, after your first iteration in a binary search, there will be 
n/2*1 items left, and 
n/2**3 items left after the third iteration. So, more generally, after x iterations, you will have n/2**x 
items left in your list.
You can use a logarithm to solve how many iterations it will take a binary search to find a number 
in a list in the worst- case scenario. For example, say you have a list with 100 numbers in it and you 
want to know how many iterations it will take a binary search to discover a number is not there. To 
answer this, you need to solve for 
n in 2**n = 100, which is the same as log
2
(100). You can solve this 
equation intuitively by guessing. For example, you might start by guessing that 
n is 5, but 2**5 is 32, 
which is too small. You can keep guessing: 2
**6 is 64, which is also too small, and 2**7 is 128, which 
is greater than 100, and is thus your answer. In other words, if you perform a binary search on a list 
with 100 items, and the item is not there, it will take your algorithm 7 steps to determine that. In 
other words, 100/2/2/2/2/2/2/2 < 1.
When you run a binary search, it divides your list in half each iteration, which means the logarithm 
describing its run time is base 2. However, in big O notation, a logarithm’s base doesn’t matter because 
you can change it by multiplying the logarithm by a constant. The math details are beyond the scope 
of this book, but the important thing to know is that the logarithm base doesn’t matter in big O 
notation. What is important is whether an algorithm is logarithmic, which usually happens when your 
algorithm reduces the computation amount by half or some other significant amount each iteration.
Because of how efficient a binary search is, if you have sorted data you need to search, it is usually 
best to use one. However, even if you have unsorted data, sometimes it is worth sorting it to take 
advantage of a binary search. For example, if you have a large list and plan to do many searches, it 
might benefit you to sort your data once to vastly speed up each one of the searches you will do in 
the future.
As with a linear search, Python has a built- in module to perform a binary search, which you should 
use when writing real- world applications. The key to writing a binary search using Python’s built- in 
tools is to use 
bisect_left
from the 
bisect
module, which finds the index of an existing element in 
a sorted list using a binary search:
from bisect import bisect_left
sorted_fruits = ['apple', 'banana', 'orange', 'plum']
bisect_left(sorted_fruits, 'banana')
>> 1