from sort import quicksort
from plot import XYPlot

dataLin = []
dataBin = []
def linearsearch(A, key):
    n = 0
    for i in range(len(A)):
        n += 1
        if A[i] == key:
            return n

    raise KeyError("item not found")

for i in range(2,101):
    listLin = range(1,i)
    #print listLin
    keyLin = len(listLin)
    nLin = linearsearch(listLin, keyLin)
    dataLin= dataLin+ [(i,nLin)]

def binarysearch(A, key):
    lo = 0
    hi = len(A) - 1
    n = 0

    while lo <= hi:
        mid = (lo + hi)/2
        n += 1

        if A[mid] < key:
            lo = mid + 1

        elif A[mid] > key:
            hi = mid - 1

        else:
            return n

    raise KeyError("value not in list!")


for j in range(2,101):
    listBin = range(1,j)
    listBin = quicksort(listBin)
    #print listBin
    keyBin = 1
    nBin = binarysearch(listBin, keyBin)
    dataBin= dataBin+ [(j, nBin)]

p = XYPlot(x_label="Number of entries in data", y_label="Number of steps required to achieve reach final point of worst case", title="Number of steps required to achieve worst case scenario for binary search and linear search")
p.add_series(dataLin, label="Linear Search")
p.add_series(dataBin, label="Binary Search")
p.show()

print("Exit")