Test the program for array sizes N = 16, 32, 64, 128, 256, 512, 1024, 2048, ……, 225. Initialize the array with random numbers between the ranges 1 through N and use the same array for testing linear search and binary search. Remember to sort the array before using binary search. Use a text file with 1,000 random numbers in the range 1 through 225 as the search keys.

Compare the execution time for linear search and binary search. Include the time taken for sorting with the binary search time (you have to sort only once for each array size). Use a table or plot to summarize the results and document your observations and explanations in the report.

Linear Serch (Python)

def linSearch(array, number):
    for x in range(0, len(array)):
        if number==array[x]:
            print(str(number) + " was found here at " + str(x))
           
sample_array = [6,9,8,10,7]
test = linSearch(sample_array, 7)
print(test)

 

Binary Search (Python)

def binSearch(sorted_array, number, min=0, max=None):
    max = max or len(sorted_array)-1
    if max < min:
        return False
    else:
        mid = min+ (max-min)/2
        mid1 = int(mid)
        if mid>number:
            return binSearch(sorted_array, number, min,
mid1-1)
        elif mid            return binSearch(sorted_array, number,
mid1+1, max)
        else:
            return mid1
           
           
           
sample_array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print((binSearch(sample_array, 9)) -1)