Skip main navigation

Linear Search vs Binary Search

In this step, we’re going to compare linear search with binary search, and see how well they perform on a variety of sorted lists when searching for specific items.

In this step, we’re going to compare linear search with binary search, and see how well they perform on a variety of sorted lists when searching for specific items.

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))

Linear Search Times vs Binary Search Times

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.

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