﻿ Comparing linear and binary search

# 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 timeitfrom random import randintlist_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 eachprint("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.

#### Programming 102: Think Like a Computer Scientist  