import time

def search_lst(L, x):
    mone = 0
    for i in range(len(L)-1):
        if x == L[i]:
            return True
    return False
    
def binary_search(L, x):
    left = 0
    right = len(L) - 1
    while left <= right:
        mid = (left + right) // 2
        if x == L[mid]:
            return True
        else:
            if x < L[mid]:  # go to left half
                right = mid - 1
            else:  # go to right half
                left = mid + 1
    return False  # if we got here the search failed
    
lst = [3, 4, 5, 6, 9, 10, 13, 16, 18, 20, 22, 28, 29, 31, 32, 33, 40, 42, 47, 48, 50, 52]
start = time.perf_counter()
result = binary_search(lst, 52)
print(result)
end = time.perf_counter()
print(end-start)
s = time.perf_counter()
result = search_lst(lst,3)
print(result)
e = time.perf_counter()
print(s-e)