The Self-Taught Computer Scientist

Chapter 3 Search Algorithms
29
In a linear search, it would have taken seven steps to find 19. It took only three steps with a binary 
search, which is less than half the number of steps.
Here is how you implement a binary search in Python:
def binary_search(a_list, n):
first = 0
last = len(a_list) - 1
while last >= first:
mid = (first + last) // 2
if a_list[mid] == n:
return True
else:
if n < a_list[mid]:
last = mid - 1
else:
first = mid + 1
return False
Your function 
binary_search
takes two arguments, 
a_list
and 
n
(the target number):
def binary_search(a_list, n):
You use the variables 
first
and 
last
to keep track of the beginning and the end of the list you are 
searching. You start by setting the value of 
first
to 0. Next, you assign the variable 
last
to the length 
of the list minus one. You will change the value of these variables as you divide 
a_list
into smaller 
and smaller segments:
first = 0
last = len(a_list) - 1
Your algorithm’s loop continues as long as there are still items in your list:
while last >= first:
Inside your loop, you locate the midpoint of 
a_list
by adding 
first
plus 
last
and then dividing by 2:
mid = (first + last) // 2
The double- slash is the floor division operator, which returns the whole value of division, rounded 
down. For example, 7 divided by 2 is 3.5, but with floor division, it is 3. You use floor division, so 
mid
is always a whole number because indexes are always whole numbers.
19
Figure 3.5: Our binary search found our number.

---

Introduction to Algorithms
30
Next, you use a conditional statement to check whether the element at the midpoint of your list is the 
element you are looking for. If it is, you return 
True
because you found the number you are looking for:
if a_list[mid] == n:
return True
If the item at the midpoint of your list is not the target item, you check whether the target item is 
greater than or less than the midpoint value. If the target item is less than the midpoint value, you set 
last
to the midpoint value minus 1, which cuts off the upper half of the list from further processing:
if n < a_list[mid]:
last = mid - 1
If the target item is greater than the midpoint value, you set the value of 
first
to the midpoint 
value plus 1, which cuts off the lower half of the list from further processing:
else:
first = mid + 1
Your loop then repeats on a smaller segment of the list you create using the variables 
first
and 
last
:
mid = (first + last) // 2
When your loop terminates, your function returns 
False
because if you’ve made it to the end of 
your function, the number is not in your iterable:
return False
When to Use a Binary Search
A binary search takes O(log 
n) time. It is more efficient than a linear search because you don’t have to 
search an entire list. Instead, you can throw out whole list segments without searching them. A binary 
search’s efficiency makes an enormous difference when you are dealing with large amounts of data. 
For example, say you are searching a list with a million numbers. If you performed a linear search, 
it might take you a million steps to complete your search. With a logarithmic binary search, on the 
other hand, it would take you only 20 steps.
Let’s take a closer look at what it means for an algorithm to be logarithmic. Exponentiation is a 
mathematical operation you write as 
b
n
(or 
b**n
in Python), where you multiply a number 
b times 
itself 
n times. In this equation, the number b is called the base, and the number n is called the expo-