# 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)