import matplotlib.pyplot as plt
import random
import time

def linearSearch(mylist, elt):
    for i in range(len(mylist)):
        if mylist[i] == elt:
            return i
    return -1

def binarySearch(mylist, elt):
    low = 0
    high = len(mylist) - 1

    # Go until the range flips (then you know you haven't found it)
    while low <= high:
        mid = (low+high) // 2 # choose the middle index
        item = mylist[mid]

        if item == elt:  # yay!
            return mid
        elif elt < item: # left half
            high = mid-1
        else:            # right half
            low = mid+1

    # No dice
    return -1

def timeBothSearches():
    nvals = [10, 20, 40, 60, 80, 100, 200, 500, 1000,
             2000, 3000, 4000, 5000, 10000, 20000, 50000,
             100000]
    linearTimes = []
    binaryTimes = []

    for n in nvals:
        print("Working on n:", n)
        
        sortedList = range(n)

        ltime = 0
        btime = 0
        numelts = 1000
        for i in range(numelts):
            element = random.choice(sortedList)
##            element = n+1

            t = time.time()

            linearSearch(sortedList, element)

            ltime += (time.time() - t)
            t = time.time()

            binarySearch(sortedList, element)
        
            btime += (time.time() - t)

        linearTimes.append(ltime / numelts * 1000)
        binaryTimes.append(btime / numelts * 1000)

    plt.figure()
    plt.plot(nvals, linearTimes, label="Linear Search Time (ms)")
    plt.plot(nvals, binaryTimes, label="Binary Search Time (ms)")
    plt.title("Search time of linear vs binary search")
    plt.xlabel("Number of elements in the list")
    plt.ylabel("Search time (ms)")
    plt.legend()
    plt.show()

def timeBinarySearch():
    nvals = [10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000]
    binaryTimes = []

    for n in nvals:
        print("Working on n:", n)
        
        sortedList = range(n)

        ltime = 0
        btime = 0
        numelts = 100000
        for i in range(numelts):
            element = random.choice(sortedList)
##            element = n+1

            t = time.time()

            binarySearch(sortedList, element)
        
            btime += (time.time() - t)
            
        binaryTimes.append(btime / numelts * 1000000)

    plt.figure()
    plt.plot(nvals, binaryTimes, label="Binary Search Time (us)")
    plt.title("Time to complete binary search as n gets really big")
    plt.xlabel("Number of elements in the list (note HUGE scale)")
    plt.ylabel("Search time (us)")
    plt.legend()
    plt.show()

if __name__ == "__main__":
    timeBothSearches()
    timeBinarySearch()