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

Comparing linear and binary search

When does a linear search find an item faster than a binary search? Investigate this with the instructions given by James Robinson in this article.
In this step, we’re going to compare linear and binary search, and see how well they perform on a variety of sorted lists when searching for specific items.
Just as we did in Week 3, we can use the timeit function in Python to find out how long it takes our two search algorithms to find a specific item.
from timeit import timeit
from random import randint

list_to_search = [i for i in range(1000000)]

#######################################################################
# COPY AND PASTE YOUR linear_search AND binary_search functions below #
#######################################################################

ls = lambda: linear_search(list_to_search, randint(0,1000000))
bs = lambda: binary_search(list_to_search, randint(0,1000000))

#time the functions for 100 runs each
print("Linear search took:")
print(timeit(ls, number = 100))

print("Binary search took:")
print(timeit(bs, number = 100))
How do the times vary when the functions are given smaller or larger lists? What happens to the time when they are asked to search for numbers that are not in the list? How about when searching for the last number in the list? Adjust the code above to try these out, and share your thoughts in the comments.
This article is from the free online

Programming 102: Think Like a Computer Scientist

Created by
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