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 #
#######################################################################
def linear_search(numbers,search_num):
    for position, item in enumerate(numbers):
        if(item == search_num):
            #print(item, " is at position ", position)
            #print("stop search at position",position)
            break
            
def binary_search(sorted_list,searched_item):
    left = 0
    #print("left",left)
    #time.sleep(2)
    right = len(sorted_list) - 1
    #print("right",right)
    #time.sleep(2)
    while(left <= right):
        mid = int((right + left) / 2)
        #print("mid",mid)
        #time.sleep(2)
        if(sorted_list[mid] > searched_item):
            right = mid - 1
            #print("left",left)
            #print("right",right)
            #time.sleep(2)
        elif(sorted_list[mid] < searched_item):
            left = mid + 1
            #print("left",left)
            #print("right",right)
            #time.sleep(2)
        elif(sorted_list[mid] == searched_item):
            return sorted_list[mid]
        else:
            return False

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

print(1000000,"numbers")
#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))

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

ls = lambda: linear_search(list_to_search, randint(0,100000))
bs = lambda: binary_search(list_to_search, randint(0,100000))
print(100000,"numbers")
#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))

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

ls = lambda: linear_search(list_to_search, randint(0,10000))
bs = lambda: binary_search(list_to_search, randint(0,10000))
print(10000,"numbers")
#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))

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

ls = lambda: linear_search(list_to_search, randint(0,1000))
bs = lambda: binary_search(list_to_search, randint(0,1000))
print(1000,"numbers")
#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))