# Allison Obourn
# CSC 110, Spring 2018
# Lecture 38

# This program searches a list for several values
# WARNING: this version is incomplete and doesn't fully work

def main():
    data = [1, 2, 3, 5, 7, 9, 22, 45, 67, 89, 234]
    print(binary_search(data, 3))
    print(binary_search(data, 4))
    print(binary_search(data, 265))

# takes a sorted list and a value as parameters.
# returns the index the value occurs at in the list
# if it is there. Returns -(index + 1) of the index
# it should be inserted at to preserve sorted order
# if it isn't there
def binary_search(data, value):
    mini = 0
    maxi = len(data) - 1
    while True:
        mid = (mini + maxi) // 2
        if data[mid] == value:
            return mid
        elif data[mid] > value:
            maxi = mid - 1
        else:
            mini = mid + 1 

main()