Python: Implementing Binary Search
Algorithm in plain English
To begin with, let’s have a look at a broad overview of how this algorithm works. We will start with asorted_list
. We will need two variables to keep track of positions in the list, left
and right
, the leftmost and rightmost items that have been checked. At the start of the algorithm, these can be set to the indices of the very start and very end of the list.
Next we need to begin a loop, within which we can try and find the index of the value
that we are looking for. When does this loop need to end? Well, as long as the left
index is less than or equal to the right
index, we know we’ve still got some searching to do (unless we’ve found the value we need, of course).
Inside the loop, we will set mid
to a midpoint halfway between left
and right
, making sure to convert to an integer position.
4.7
sorted_list
at the mid
position is greater than the value we are looking for, then we can set right
to be the same as mid
point.
If the item in the sorted_list
at the mid
position is less than the value we are looking for, then we can set left
to be the same as the mid
point.
If neither of these conditions holds, then we must have found the value
and the mid
point can be returned.
If we haven’t found the value
, the loop will continue (or if it ends, it means the value
wasn’t in the list at all).
If you feel that you now have enough information to implement the algorithm, then have a go at doing it yourself. If it works, skip to the end of this section to look at the additional challenges.
Structured English algorithm
Writing an algorithm in structured English can often help you develop your code. It can often be used as the basis for comments in you final code.
 Set
left
to0
 Set

 Set
right
to highest index in list
 Set

 Create a loop that ends when
left
greater thanright
 Create a loop that ends when

 Set
mid
to be an integer half way betweenleft
andright
 Set

 If the item in
sorted_list
at themid
position is greater than thevalue
we are after, setright
to bemid
– 1
 If the item in

 If the item in
sorted_list
at themid
position is less than thevalue
we are after, setleft
to bemid
+ 1
 If the item in

 If the item in
sorted_list
at themid
position is equal to thevalue
we are after, return themid
position
 If the item in

 If the loop ends, return
False
to indicate thevalue
was not found
 If the loop ends, return
Coding the algorithm

 Let’s start by taking a cutdown version of the structured English above, and use it as comments in our code.
# left to 0
# right to highest index in list
# loop that ends when left > right
# mid to int between left and right
# if sorted_list[mid] > value set right to mid  1
# if sorted_list[mid] < value set left to mid  1
# if sorted_list[mid] == value return mid
# loop ends return `False`

 Now we can start filling in the gaps with real code, beginning with a function definition.
def binary_search(sorted_list, value):
# left to 0
# right to highest index in list
# loop that ends when left > right
# mid to int between left and right
# if sorted_list[mid] > value set right to mid
# if sorted_list[mid] < value set left to mid
# if sorted_list[mid] == value return mid
# loop ends return `False`

 Next we can create the first two variables.
def binary_search(sorted_list, value):# left to 0
left = 0# right to highest index in list
right = len(sorted_list)  1# loop that ends when left > right
# mid to int between left and right
# if sorted_list[mid] > value set right to mid
# if sorted_list[mid] < value set left to mid
# if sorted_list[mid] == value return mid
# loop ends return `False`

 Now let’s set up the loop and create the
mid
variable.
 Now let’s set up the loop and create the
def binary_search(sorted_list, value):# left to 0
left = 0# right to highest index in list
right = len(sorted_list)  1# loop that ends when left > right
while left <= right:# mid to int between left and right
mid = int((right + left)/2)# if sorted_list[mid] > value set right to mid
# if sorted_list[mid] < value set left to mid
# if sorted_list[mid] == value return mid
# loop ends return `False`

 Adding in those conditionals, we get the following:
def binary_search(sorted_list, value):# left to 0
left = 0# right to highest index in list
right = len(sorted_list)  1# loop that ends when left > right
while left <= right:# mid to int between left and right
mid = int((right + left)/2)# if sorted_list[mid] > value set right to mid
if sorted_list[mid] > value:right = mid  1# if sorted_list[mid] < value set left to mid
elif sorted_list[mid] < value:left = mid + 1# if sorted_list[mid] == value return mid
else:return mid# loop ends return `False`

 And if the loop ends we return
False
:
 And if the loop ends we return
def binary_search(sorted_list, value):# left to 0
left = 0# right to highest index in list
right = len(sorted_list)  1# loop that ends when left > right
while left <= right:# mid to int between left and right
mid = int((right + left)/2)# if sorted_list[mid] > value set right to mid
if sorted_list[mid] > value:right = mid  1# if sorted_list[mid] < value set left to mid
elif sorted_list[mid] < value:left = mid + 1# if sorted_list[mid] == value return mid
else:return mid# loop ends return `False`
return False

 Removing all the comments, we are left with the following:
def binary_search(sorted_list, value):left = 0right = len(sorted_list)  1while left <= right:mid = int((left + right)/2)if sorted_list[mid] > value:right = mid  1elif sorted_list[mid] < value:left = mid + 1else:return midreturn False
from random import randintsorted_list = [i + randint(0,9) for i in range(0,100,10)]
Challenge
Now that you have created your binary search algorithm in Python, it’s time to have a think about a few improvements that can be made.

What if there is a run of the same values in a list? For example, in the list
[1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 9]
, if you search for the value4
, which index is returned? Can you alter your code so that it will always return the leftmost item when there are multiple identical values? How about the rightmost?

What if there is a run of the same values in a list? For example, in the list

Can you return the index of the closest value, when the actual value is not found? So in the list
[1,2,3,5,6,7]
, if I searched for3.5
then2
would be returned, because at index2
the value is3
which is closest to3.5
.
Programming 102: Think Like a Computer Scientist
Our purpose is to transform access to education.
We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.
We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.
Learn more about how FutureLearn is transforming access to education