# BinarySearch_Iterative.py

def binarySearch(aList, target):
  """
     binarySearch (iterative)
     Precondition: list must be sorted
  """
  position = -1 # returning the index of target or -1 (out of range value)
  first = 0 # index representing the start of list
  last = len(aList) - 1 # index representing the end of list
  count = 0 # counting how many time is the critical operations executed
  targetNotFound = True
  # loop until all elements of list have either been discarded or compared
  while targetNotFound and first <= last:
    mid = (first + last) // 2 # determine middle of list
    count += 1
    if aList[mid] == target : # target found …
      position = mid  # returns index of list element containing target
      targetNotFound = False      
    # otherwise, target must be in second half of list
    elif aList[mid] < target :  first = mid + 1
    # otherwise, target must be in first half of list
    elif aList[mid] > target :  last = mid - 1
  return position, count # return invalid index if target not in list

# Main part of program
print("Test case #1")
aList = [1, 3, 4, 7, 9, 11, 12, 14, 21]
target = 7
result, count = binarySearch(aList, target)
if result >= 0:
  print("Looking for {0} in {1} and found it at index {2} after executing the critical operation {3} times.".format(target, aList, result, count))
else:
  print("{0} NOT FOUND in {1} after executing the critical operation {2} times.".format(target, aList, count))  
print("Test case #2")
aList = [1, 3, 4, 7, 9, 11, 12, 14, 21]
target = 24
result, count = binarySearch(aList, target)
if result >= 0:
  print("Looking for {0} in {1} and found it at index {2} after executing the critical operation {3} times.".format(target, aList, result, count))
else:
  print("{0} NOT FOUND in {1} after executing the critical operation {2} times.".format(target, aList, count)) 
print("Test case #3")
aList = [1, 3, 4, 7, 9, 11, 12, 14, 21]
target = 1
result, count = binarySearch(aList, target)
if result >= 0:
  print("Looking for {0} in {1} and found it at index {2} after executing the critical operation {3} times.".format(target, aList, result, count))
else:
  print("{0} NOT FOUND in {1} after executing the critical operation {2} times.".format(target, aList, count)) 
print("Test case #4")
aList = [1, 3, 4, 7, 9, 11, 12, 14, 21]
target = 21
result, count = binarySearch(aList, target)
if result >= 0:
  print("Looking for {0} in {1} and found it at index {2} after executing the critical operation {3} times.".format(target, aList, result, count))
else:
  print("{0} NOT FOUND in {1} after executing the critical operation {2} times.".format(target, aList, count))