# 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.