Linear and Binary Search Execution Time

'''
CHAPTER 1
'''

def binarySearch(A, u, low, high):
    if low > high:
        return None
    mid = (low + high) // 2
    if u == A[mid]:
        return mid
    if u > A[mid]:
        return binarySearch(A, u, mid + 1, high)
    else:
        return binarySearch(A, u, low, mid - 1)

def linearSearch(A, u):
    n = len(A)
    flag = False
    for i in range(n):
        if u == A[i]:
            flag = True
            return i
    if flag == False:
        return None


# MAIN FUNCTION
myList = list(range(1, 100))
print("Index of 38 (binarySearch): " + str(binarySearch(myList, 38, 0, len(myList))))
print("Index of 50 (binarySearch): " + str(binarySearch(myList, 50, 0, len(myList))))
print("Index of 88 (binarySearch): " + str(binarySearch(myList, 88, 0, len(myList))))
print("Index of -100 (binarySearch): " + str(binarySearch(myList, -100, 0, len(myList))))
print("Index of 38 (linearSearch): " + str(linearSearch(myList, 38)))
print("Index of 50 (linearSearch): " + str(linearSearch(myList, 50)))
print("Index of 88 (linearSearch): " + str(linearSearch(myList, 88)))
print("Index of -100 (linearSearch): " + str(linearSearch(myList, -100)))


'''
CHAPTER 2
'''

# Create a sorted list with elements form 1 to 1.000.000
newList = list(range(1, 1000001))
from timeit import default_timer as timer
executions = list(range(100000, 1100000, 100000))
# executions = [100, 200, 300, .... , 900, 1000]
measurements_lsearch = []
measurements_bsearch = []
for num in executions:
    start1 = timer()
    linearSearch(newList[0:num], -100);
    end1 = timer()
    measurements_lsearch.append(end1 - start1)
    start2 = timer()
    binarySearch(newList[0:num], -100, 0, len(newList[0:num]) - 1);
    end2 = timer()
    measurements_bsearch.append(end2 - start2)

print("Executions    Time_linearSearch in ms       Time_binarySearch in ms")
for execution, m1, m2 in zip(executions, measurements_lsearch, measurements_bsearch):
    print(str(execution) + "          " + str(m1 * 1000) + "          " + str(m2 * 1000))



'''
CHAPTER 3
'''

import matplotlib.pyplot as plt
plt.plot(executions, measurements_lsearch, label = "Linear Search")
plt.plot(executions, measurements_bsearch, label = "Binary Search")
plt.xlabel("Number of Elements")
plt.ylabel("Execution Time")
plt.legend()