CompareBinaryAndLinearSearch

from timeit import timeit
from random import randint


def linear_search(alist,value):
    for position, item in enumerate(alist):
        #print(item, "is at position", position)
        if item == value:
            return position
    return False

def binary_search(sorted_list, value):
    left = 0
    right = len(sorted_list) - 1
    while left <= right:
        mid = int((left + right)/2)
        if sorted_list[mid] > value:
            right = mid - 1
        elif sorted_list[mid] < value:
            left = mid + 1
        else:
            return mid
    return False

#Create anonymous functions to use with timeit
bs = lambda: binary_search(list_to_sort, value_to_find)
ls = lambda: linear_search(list_to_sort, value_to_find)

print('List size:   Linear                 Binary            Ratio (linear/binary)')

for list_size in [5, 10,20,30,50,100,200,500,1000]:
    slin=0
    sbin=0
    for i in range(100):
        #sGenerate a large (1000 items) random list
        list_to_sort = [randint(0,list_size) for i in range(list_size)]
        #sort list
        list_to_sort = sorted(list_to_sort)
        #list_to_sort = [1,2,4,6,7,8,1,12,13,14]
        value_to_find=randint(0,list_size)
        slin+=timeit(ls, number = 100)
        sbin+=timeit(bs, number = 100)

    print(list_size,(slin/100), (sbin/100), slin/sbin)

print('not found')
for list_size in [5, 10,20,30,50,100,200,500,1000]:
    slin=0
    sbin=0
    for i in range(100):
        #sGenerate a large (1000 items) random list
        list_to_sort = [randint(0,list_size) for i in range(list_size)]
        #sort list
        list_to_sort = sorted(list_to_sort)
        #list_to_sort = [1,2,4,6,7,8,1,12,13,14]
        value_to_find= 32.5#list_size+1
        slin+=timeit(ls, number = 100)
        sbin+=timeit(bs, number = 100)

    print(list_size,(slin/100), (sbin/100), slin/sbin)