import random

# return True if key is found
# return False if key is not found
# alist is assumed to be sorted low to high
def binary_search(alist, key):

    count = 0
    starti = 0
    endi = len(alist) - 1

    while starti <= endi:
        count += 1
        midi = (starti + endi) // 2

        if key == alist[midi]:
            return True, count
        elif key < alist[midi]:
            # we want to focus on the left portion now
            endi = midi - 1
        else:
            # we want to focus on the right portion
            starti = midi + 1

    return False, count # if we never found key we will get here

mylist = []
size = 4096

for _ in range(size):
    mylist.append(random.randint(1,10000))

mylist.sort()

lookfor = 5000

returned_answer = binary_search(mylist, lookfor)
print(f'Binary search did {returned_answer[1]} loop iterations.')

if returned_answer[0]:
    print('Found it')
else:
    print('Didn\'t find it')