# File:    binarySearch.py
# Author:  Dr. Gibson
# Date:    5/3/2017
# Section: N/A
# E-mail:  k.gibson@umbc.edu 
# Description:
#   This file contains python code that uses recursion
#   to complete a binary search.


def binSearch(myList, item):
    ##############
    # BASE CASES
    # we've run out of things to search for
    if len(myList) == 0:
        return False

    # need to know the middle of the list
    middleIndex = len(myList) // 2
    middleItem = myList[ middleIndex ]

    # we've found the item
    if item == middleItem:
        return True

    ###################
    # RECURSIVE CASES
    # if the item is greater than the middle of the list
    elif item > middleItem:
        # RECURSIVE CALL
        return binSearch(myList[middleIndex + 1 : ], item)
    # if the item is less than the middle of the list
    else:
        return binSearch(myList[ : middleIndex ], item)



def main():
    myList = list(range(1, 401, 3))

    num = 37
    ans = binSearch(myList, num)

    print("Found", num, "?", ans)


main()