# searches.py # Implementation of linear and binary searches def linSearch(x, nums): for i in range(len(nums)): if nums[i] == x: # item found, return the index value return i return -1 # loop finished, item was not in list def binSearch(x, nums): low = 0 high = len(nums)-1 while low <= high: # There is still a range to search mid = (low + high)//2 # position of middle item item = nums[mid] if x == item : # Found it! Return the index return mid elif x < item: # x is in lower half of range high = mid - 1 # move top marker down else: # x is in upper half low = mid + 1 # move bottom marker up return -1 # no range left to search, x is not there def recBinSearch(x, nums, low, high): if low > high: # No place left to look, return -1 return -1 mid = (low + high) // 2 item = nums[mid] if item == x: # Found it! Return the index return mid elif x < item: # Look in lower half return recBinSearch(x, nums, low, mid-1) else: # Look in upper half return recBinSearch(x, nums, mid+1, high) def rbinSearch(x, nums): return recBinSearch(x, nums, 0, len(nums)-1) import time, random # Simple test function. You can use this interactively to time different # size searches. Here's an example call: # >>> from searches import * # >>> avgTime(binSearch, 5000, 10) # This reports the average time needed to find a random value in a list # of 5000 ints. The average is done over 10 trials. def avgTime(search, n, trials): # build an ordered list of size n l1 = list(range(n)) print("List built") # run a number of trials and compute average time sum = 0.0 for i in range(trials): print(i+1, end=' ') # show progress target = random.randint(0,n) # Get system time just before search t0 = time.time() pos = search(target, l1) # Get system time just after search t1 = time.time() # Add elapsed time to sum sum = sum + (t1-t0) print("\naverage:", sum/trials)