We use cookies to give you a better experience. Carry on browsing if you're happy with this, or read our cookies policy for more information.

Skip main navigation
Home / IT & Computer Science / Coding & Programming / Programming 102: Think Like a Computer Scientist / Python: Implementing Binary Search

Python: Implementing Binary Search

James Robinson provides advice in this article to help you implement a binary search in Python.
In this article, you’re going to implement the binary search algorithm. The article will walk you through how to program it in Python, and then ask you to make a few small improvements to it at the end.

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 a sorted_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.

Want to keep
learning?

This content is taken from
Raspberry Pi Foundation online course,

Programming 102: Think Like a Computer Scientist

View Course
 
If the item in the 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.
 
 
    1. Set left to 0
 
    1. Set right to highest index in list
 
    1. Create a loop that ends when left greater than right
 
    1. Set mid to be an integer half way between left and right
 
    1. If the item in sorted_list at the mid position is greater than the value we are after, set right to be mid – 1
 
    1. If the item in sorted_list at the mid position is less than the value we are after, set left to be mid + 1
 
    1. If the item in sorted_list at the mid position is equal to the value we are after, return the mid position
 
    1. If the loop ends, return False to indicate the value was not found
 
 
If this is enough for you, try writing the algorithm in Python. Then if it works as planned have a go at the challenges at the bottom of the page.
 

Coding the algorithm

 
 
    • Let’s start by taking a cut-down 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.
 
 
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:
 
 
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
 
You can test your function by calling it, making sure that you are passing in an ordered list and a value to search for. Here’s a quick way to create an ordered list of numbers.
 
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.
 
 
    1. 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 value 4, 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?
       
 
  1. 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 for 3.5 then 2 would be returned, because at index 2 the value is 3 which is closest to 3.5.
Share your solutions and ideas in the comments, and don’t forget to ask for help if you need it.

Want to keep learning?

This content is taken from Raspberry Pi Foundation online course
Programming 102: Think Like a Computer Scientist
View Course
See other articles from this course
This article is from the online course:

Programming 102: Think Like a Computer Scientist

Created by
Join For Free

News categories

Other top stories on FutureLearn

FutureLearn offers courses in many different subjects such as

This article is from the free online

Programming 102: Think Like a Computer Scientist

Created by
Join For Free
FutureLearn - Learning For Life

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

Register to receive updates

  • Create an account to receive our newsletter, course recommendations and promotions.

    Register for free