# File:    binSearch.py
# Author:  Dr. Gibson
# Date:    11/30/2016
# 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
    if len(myList) == 0:
        # never found it, boo! :(
        return False
    
    middle = len(myList) // 2
    # we found the item, yay! :)
    if myList[middle] == item:
        return True

    # RECURSIVE CASES
    if myList[middle] > item:
        # it's probably in the front half
        return binSearch(myList[ : middle], item)
    else:
        return binSearch(myList[middle + 1 : ], item)
    


def main():
    myList1 = [1, 2, 3, 5, 7]
    myList2 = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

    ans = binSearch(myList1, 5)
    print(ans)

main()