from timeit import timeit
from random import randint

list_to_search = [i for i in range(1000000)]
value = 30

def linear_search(list_to_search, value):
    for i in range(len(list_to_search)):
        if list_to_search[i] == value:
            return

def binary_search(list_to_search, value):
    left = 0
    right = len(list_to_search)-1
    while left <= right:
        mid = int((left+right)/2)
        if list_to_search[mid] > value:
            right = mid - 1
        elif list_to_search[mid] < value:
            left = mid + 1
        else:
            return mid

    return False

position = binary_search(list_to_search, value)

if position !=- 1:
    print(str(value),"found at position", position)
else:
    print("not found")


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