""" searching.py examples of searching a list for a given value $ python searching.py -- searching.py -- a random array: [46, 60, 40, 46, 59, 50, 63, 38] linear search for 10 in [5, 8, 10, 20, 30] : i=2. binary search for 10 in [5, 8, 10, 20, 30] : i=2. n_trials=2, elapsed=0.0 n_trials=4, elapsed=0.0719606876373291 n_trials=8, elapsed=0.14397525787353516 n_trials=16, elapsed=0.2801327705383301 n_trials=32, elapsed=0.5522933006286621 time for linear n=1000000 is 0.03455341. n_trials=2, elapsed=0.0 n_trials=4, elapsed=4.00543212890625e-05 n_trials=8, elapsed=5.2928924560546875e-05 n_trials=16, elapsed=5.1975250244140625e-05 n_trials=32, elapsed=7.605552673339844e-05 n_trials=64, elapsed=0.00010013580322265625 n_trials=128, elapsed=0.00016188621520996094 n_trials=256, elapsed=0.00029778480529785156 n_trials=512, elapsed=0.0005388259887695312 n_trials=1024, elapsed=0.0011131763458251953 n_trials=2048, elapsed=0.0021419525146484375 n_trials=4096, elapsed=0.004206180572509766 n_trials=8192, elapsed=0.008191108703613281 n_trials=16384, elapsed=0.01651906967163086 n_trials=32768, elapsed=0.031621694564819336 n_trials=65536, elapsed=0.06403422355651855 n_trials=131072, elapsed=0.12969589233398438 n_trials=262144, elapsed=0.2576608657836914 n_trials=524288, elapsed=0.515794038772583 time for binary n=1000000 is 0.00000196. Jim Mahoney | cs.bennington.college | MIT License | Feb 2022 """ from random import randint from time import time def search_linear(x, items): """ search for x in items. If found, return its index; else return None """ # Implemented with a linear i.e. items[0], items[1], ... search. # Quick quiz: what O() behavior do you expect this to have? for i in range(len(items)): # Look at each array item in turn. if items[i] == x: # Found x; return the index. return i return None # Looked at all of 'em; x not found. def search_binary(x, items): """ search for x in an ordered list. Return its index if found else Nonen """ # Implemented with a binary search in an explicit loop. # Quick quiz: what O() behavior do you expect this to have? i_low = 0 i_high = len(items) - 1 while i_low <= i_high: # Still a range of indeces to search? i_mid = (i_low + i_high)//2 # Index of middle of remaining range. item = items[i_mid] if x == item : # Found it! Return the index. return i_mid elif x < item: # x is in lower half of range, so i_high = i_mid - 1 # move top marker down. else: # x is in upper half, so i_low = i_mid + 1 # move bottom marker up. return None # No place left to search => x is missing. def get_small_large(n): """ return (smallest, largest) used by the other functions here """ return (1, n*n) def random_numbers(n): """ return a list of of n random integers """ (smallest, largest) = get_small_large(n) result = [0] * n # allocate an empty indexed array for i in range(n): # fill it with randoms result[i] = randint(smallest, largest) return result def random_number(n): """ return a random integer """ (smallest, largest) = get_small_large(n) return randint(smallest, largest) def average_time(func, n, verbose=False): """ Return the average time it takes to run func(x, random_numbers(n)) """ # If the function runs too fast, we run it in many trials, then # divide by the number of trials in order to get reasonable timing. n_trials = 1 elapsed_seconds = 0.0 enough_seconds = 1.0 while elapsed_seconds < enough_seconds: n_trials = n_trials * 2 numbers = sorted(random_numbers(n)) # in case we do binary search number = random_number(n) start = time() if verbose: print(f" n_trials={n_trials}, elapsed={elapsed_seconds}") for i in range(n_trials): result = func(number, numbers) stop = time() elapsed_seconds = stop - start return elapsed_seconds / n_trials def main(): print("-- searching.py --") print(f"a random array: {random_numbers(8)}") x = 10 xs = [5, 8, 10, 20, 30] print(f"linear search for {x} in {xs} : i={search_linear(x, xs)}.") print(f"binary search for {x} in {xs} : i={search_binary(x, xs)}.") n = 1000000 linear_time = average_time(search_linear, n, verbose=True) print(f"time for linear n={n} is {linear_time:.8f}.") binary_time = average_time(search_binary, n, verbose=True) print(f"time for binary n={n} is {binary_time:.8f}.") if __name__ == "__main__": main()