Test the program for array sizes N = 16, 32, 64, 128, 256, 512, 1024, 2048, ,
Question:
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)
Applied Statistics in Business and Economics
ISBN: 978-0073521480
4th edition
Authors: David Doane, Lori Seward