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