def sequential_search(lst, key):
    """ Iterate lst sequentially to search for key
        lst need not be sorted for sequential search to work.
        returns index of match or None if not found """
    for i in range(len(lst)):
        if lst[i] == key:
            return i

    #We get here when the key is not in the list
    #print(key, "not found")
    return None  



def sequential_search_back(lst, key):
    lst = lst[::-1] # reversed lst
    for i in range(len(lst)):
        if lst[i] == key :
            return len(lst)-i-1

    #We get here when the key is not in the list
    #print(key, "not found")
    return None




def binary_search(lst, key):
    """ lst better be sorted for binary search to work """
    n = len(lst)
    left = 0
    right = n-1

    while left <= right:
        mid = (left+right)//2    # middle rounded down
        if key == lst[mid]:      # item found
            return mid
        elif key < lst[mid]:     # item cannot be in top half
            right = mid-1
        else:                    # item cannot be in bottom half
            left = mid+1           

    #print(key, "not found")
    return None  



####################################################
## Time measurements of sequential vs. binary search
####################################################


import time

REPEAT = 20 #repeat execution several times, for more significant statistics

for f in [sequential_search, binary_search]:
    print(f.__name__)

    for n in [10**6, 2*10**6, 4*10**6]:
        print("n=", n)

        L = [i for i in range(n)] #generates the ordered list 0,1,2,...,n-1
        key = -1 #key that DOES NOT exist in the list (worst case)

        t0 = time.perf_counter()
        for i in range(REPEAT): 
            res = f(L, key) # key not found
        t1 = time.perf_counter()
        print("time for", REPEAT, "executions:", (t1-t0))