from timeit import timeit
from random import randint
import matplotlib.pyplot as plt
import logging

num_iterations = 500

def linear_search (a_list, an_item):
    result = -1 # an_item not found
    for position, value in enumerate(a_list):
        if value == an_item:
            result = position
            break
        if value > an_item:
            break
    return position

def binary_search(sorted_list, item_to_find):
    left = 0
    list_len = len(sorted_list) - 1
    right = list_len
    result = False
    num_iter = 0;
    pos_list = []
    near_pos = -1
    min_diff = 1e20

    while left <= right:
        num_iter +=1
        mid = int((left + right)/2)
        diff = abs(sorted_list[mid]-item_to_find)
        if diff < min_diff:
            min_diff = diff
            near_pos = mid
        if sorted_list[mid] > item_to_find:
            right = mid - 1
        elif sorted_list[mid] < item_to_find:
            left = mid + 1
        else:
            result = True
            break
    if result: #Check for multiples
        pos_list.append(mid)
        left = mid-1
        while (sorted_list[left] == item_to_find) and (left >= 0):
            pos_list.append(left)
            left -= 1
        right = mid + 1
        if right <= list_len:
            while (right <= list_len) and (sorted_list[right] == item_to_find):
                pos_list.append(right)
                right += 1
        pos_list = sorted(pos_list)
    #print('result='+str(result) + ' mid=' + str(mid) + ' sl='+str(sorted_list[mid]))
    return result, sorted_list[mid], pos_list, num_iter, near_pos

def srch_times_for_list(a_list, list_len, l_list, b_list, percent):
    if percent > 1:
        num_to_find = list_len
    else:
        idx = (list_len-1) * percent
        logging.debug('Idx = '+ str(idx))
        #print('Idx = '+ str(idx))
        idx = int(idx)
        if idx >= list_len:
            idx = list_len -1;
        #print('Idx = '+ str(idx))
        num_to_find = a_list[idx]
    #print("List Length = " + str(list_len) + " Searching for " + str(num_to_find) + " percent = " + str(percent))

    ls = lambda: linear_search(a_list, num_to_find)
    bs = lambda: binary_search(a_list, num_to_find)
    l_list.append(timeit(ls, number = num_iterations))
    b_list.append(timeit(bs, number = num_iterations))
    return l_list, b_list
"""
list_to_search = [i for i in range(1000000)]
ls = lambda: linear_search(list_to_search, randint(0,1000000))
bs = lambda: binary_search(list_to_search, randint(0,1000000))
"""

#generate some data
y=[]; x0l=[]; x0b=[]; x25l=[]; x25b=[]; x50l=[]; x50b=[]
x75l=[]; x75b=[]; x100l=[]; x100b=[]; x105l=[]; x105b=[]

ii = 10

while ii <= 30000:
    y.append(ii)
    list_to_search = [ i for i in range(ii)]
    x0l, x0b = srch_times_for_list(list_to_search,ii, x0l, x0b,0)
    x25l, x25b = srch_times_for_list(list_to_search,ii, x25l, x25b,0.25)
    x50l, x50b = srch_times_for_list(list_to_search,ii, x50l, x50b,0.50)
    x75l, x75b = srch_times_for_list(list_to_search,ii, x75l, x75b,0.75)
    x100l, x100b = srch_times_for_list(list_to_search,ii, x100l, x100b,1.0)
    x105l, x105b = srch_times_for_list(list_to_search,ii, x105l, x105b,1.05)
    ii = ii + 2000

plt.style.use('seaborn-whitegrid')
#fig1, (ax1, ax2, ax3, ax4) = plt.subplots(1,4 , sharex=True, sharey=True)
fig1, (ax1, ax2) = plt.subplots(1,2 , sharey=True)

ax1.plot(x0l, y,  label='search[0%]')
ax1.plot(x25l, y, label='search[25%]')
ax1.plot(x50l, y, label='search[50%]')
ax1.plot(x75l, y, label='search[75%]')
ax1.plot(x100l, y, label='search[100%]')
ax1.plot(x105l, y, label='not in list')
ax1.legend(loc='lower right')
ax1.set(xlabel='time (sec) ' + str(num_iterations) + ' Iterations', ylabel='Length of list (number of points)',
       title='linear')

ax2.plot(x0b, y, label='search[0%]')
ax2.plot(x25b, y, label='search[25%]')
ax2.plot(x50b, y, label='search[50%]')
ax2.plot(x75b, y, label='search[75%]')
ax2.plot(x100b, y,label='search[100%]')
ax2.plot(x105b, y,label='not in list')
ax2.legend(loc='upper left')
ax2.set(xlabel='time (sec) ' + str(num_iterations) + ' Iterations', ylabel='Length of list (number of points)',
       title='binary')

fig1.set_size_inches(9.5, 8.5)
fig1.show()


print()