4.9

# Comparing linear and binary search

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.