Question

Using your solution to Lab 11A, write a program that counts how many steps to find the number 9467 in a list of size 20000 (using unique random numbers in the range 1 through 321000). Then double the list size to 40000 and count the steps taken to find the same number, then keep doubling the list size until the list size is 320000. For each list size, find how many steps to find the number 9467. Your program should print the list size followed by the number of steps, for each list size... NOTE: it may take several minutes for the program to complete its output. Be patient! The output should look similar to this: Length of list: 20000 Steps: 14 NOT Found! Length of list: 40000 Steps: 15 NOT Found! Length of list: 80000 Steps: 16 NOT Found! Length of list: 160000 Steps: 1 NOT Found! Length of list: 320000 Steps: 1 NOT Found! >>>

Use Python 3

11a is using the binary search program that counts steps amend the program so that a list of size 10000 is made - using unique random numbers in the range 1 through 20000. Test how many steps to find the number 9467.

Answer 1

Code:

import numpy as np
def binarySearch(a, value):
f = 0
step = 0
l = len(a)-1
flag = False
  
while f<=l and not flag:
m = (f + l)//2
if a[m] == value:
flag = True
else:
if value < a[m]:
l = m-1
else:
f = m + 1
step = step + 1

print("Length of list :",len(a),"Steps :",step)
if flag == False :
print("Not Found")
else:
print("Found")
  
if __name__=="__main__":
for i in range(5):
r = randnums= np.random.randint(1,20000*pow(2,i),20000*pow(2,i))
binarySearch(r, 9467)

Output Snapshot:

Length of list : 20000 Steps : 14 Not Found Length of list : 40000 Steps : 15 Not Found Length of list : 80000 steps : 16 Not Found Length of list : 160000 Steps : 17 Not Found Length of list : 320000 Steps : 18 Not Found