#
# binary search with numbers, and comparison to 2 types of linear search
# of an ordered list
#
# it generates a list of numbers in order and then searches that
#
#
# external modules this needs
#
import sys
import random
#
# useful variables
#
maxnum = 100 # how many numbers to search
smallest = -100 # smallest number in the list
bcmpcount = 0 # number of numbers in list compared for binary search
l1cmpcount = 0 # number of numbers in list compared for ordinary linear
# search
l2cmpcount = 0 # number of numbers in list compared for linear search
# that stops when the number being searched for is
# less than the current number
#
# this builds the list
# arguments: X -- list; it must be empty
#
def buildlist(X):
# set starting point
next = smallest
# advance by a random number and append
# the new number to the list
for k in range(0, maxnum):
next += random.randrange(1, 10)
X.append(next)
# print the sorted list, so users can pick a starting guess
print("sorted list:", X)
#
# binary search routine (recursive)
#
def binsearch(L, num):
global bcmpcount # refers to outsidde bmpcount
# do this recursively
# first, see if you're at the base case
if L == []:
return False
if len(L) == 1:
bcmpcount += 1
return num == L[0]
# find the midpoint
midpt = len(L) // 2
# now see if it's in the middle, or the left or right half
bcmpcount += 1
if num == L[midpt]:
return True
elif num < L[midpt]:
return binsearch(L[:midpt], num)
elif num > L[midpt]:
return binsearch(L[midpt+1:], num)
else: # should never happen
print("The universe has failed;", num, "neither ==, <, or >", L[midpt])
sys.exit(1)
#
# linear search -- if missing, it goes to the end
#
def lin1search(L, num):
global l1cmpcount # refers to outside l1count
# figure out how long the array is
p = len(L)
# go down the list
for i in range(0,p):
# see if this is the one
l1cmpcount += 1
if num == L[i]:
return True
# if you get here, it's not in the list
return False
#
# linear search -- if missing, it stops at thee first larger number
#
def lin2search(L, num):
global l2cmpcount # refers to outside l2count
# figure out how long the array is
p = len(L)
# go down the list
for i in range(0,p):
# see if this is the one
l2cmpcount += 1
if num == L[i]:
return True
# it isn't the one
# if the list element is larger,
# the number is not in the list
if num < L[i]:
return False
# if you get here, it's not in the list
return False
#
# the fount of all things
def main():
global bcmpcount, l1cmpcount, l2cmpcount; # refers to outside counters
# build the list of ordered numbers
L = list()
buildlist(L)
# now loop until you get an EOF
while True:
# read in an integer, catcing EOF (exit) and other exceptions
# (go back and ask for an integer)
try:
tofind = int(input("Enter an integer: "))
except EOFError:
break;
except:
print("An *integer*, please!")
continue
# do a binary search and report result and count
if binsearch(L, tofind):
print(tofind, "is in the list --", bcmpcount, "numbers checked (binary)")
else:
print(tofind, "is not in the list --", bcmpcount, "numbers checked (binary)")
# do a linear search and report result and count
if lin1search(L, tofind):
print(tofind, "is in the list --", l1cmpcount, "numbers checked (linear)")
else:
print(tofind, "is not in the list --", l1cmpcount, "numbers checked (linear)")
# do a linear search, stopping when you know it isn't in
# the list and report result and count
if lin2search(L, tofind):
print(tofind, "is in the list --", l2cmpcount, "numbers checked (linear stopping)")
else:
print(tofind, "is not in the list --", l2cmpcount, "numbers checked (linear stopping)")
# reset all counters for next time through the loop
bcmpcount = l1cmpcount = l2cmpcount = 0
#
# and off we go!
#
main()