# BinarySearch_Recursive.py

def BinarySearch(aList, target, low, high):
  """
     binarySearch (recursive)
     Precondition: list must be sorted
  """
  TARGET_ELEMENT_NOT_FOUND  = -1
  if high < low :
    result = TARGET_ELEMENT_NOT_FOUND   
  else:
    mid = (low + high) // 2 
    if aList[mid] > target : 
        result = BinarySearch(aList, target, low, mid-1) 
    elif aList[mid] < target :
        result = BinarySearch(aList, target, mid+1, high) 
    else: 
        result = mid   # target found 
  return result

# Main part of program
aList = [1, 3, 4, 7, 9, 11, 12, 14, 21]
target = 7
low = 0
high = len(aList)-1
result = BinarySearch(aList, target, low, high)
if result >= 0:
  print("Looking for {0} in {1} and found it at index {2}.".format(target, aList, result))
else:
  print("{0} NOT FOUND in {1}.".format(target, aList))  
aList = [1, 3, 4, 7, 9, 11, 12, 14, 21]
target = 24
low = 0
high = len(aList)-1
result = BinarySearch(aList, target, low, high)
if result >= 0:
  print("Looking for {0} in {1} and found it at index {2}.".format(target, aList, result))
else:
  print("{0} NOT FOUND in {1}.".format(target, aList))    
aList = [1, 3, 4, 7, 9, 11, 12, 14, 21]
target = 1
low = 0
high = len(aList)-1
result = BinarySearch(aList, target, low, high)
if result >= 0:
  print("Looking for {0} in {1} and found it at index {2}.".format(target, aList, result))
else:
  print("{0} NOT FOUND in {1}.".format(target, aList))  
aList = [1, 3, 4, 7, 9, 11, 12, 14, 21]
target = 21
low = 0
high = len(aList)-1
result = BinarySearch(aList, target, low, high)
if result >= 0:
  print("Looking for {0} in {1} and found it at index {2}.".format(target, aList, result))
else:
  print("{0} NOT FOUND in {1}.".format(target, aList))