# binSrch.py

def binSearch(elems, v):
  return binSrch(elems, v, 0, len(elems)-1)


def binSrch(elems, v, left, right):
  if left > right:  # list exhausted without a match
    return -1

  mid = (left + right)//2
  if v < elems[mid]:
    return binSrch(elems, v, left, mid-1)
  elif v == elems[mid]:
    return mid
  else:
    return binSrch(elems, v, mid+1, right)


def binSearchIter(elems, v):
  left = 0
  right = len(elems) - 1 # Last index in elems
    
  while left <= right:
    mid = (left + right)//2
    if v < elems[mid]:
      right = mid-1
    elif v == elems[mid]:
      return mid
    else:
      left = mid+1
  return -1   # right < left, v not found


if __name__ == "__main__":
  elems = [2, 4, 5, 7, 8, 9, 12, 14, 17, 19, 22, 25, 27, 28, 33, 37]
  print(binSearch(elems, 3))
  print(binSearch(elems, 22))

  print(binSearchIter(elems, 22))