Iterative and Recursive Binary Search

binary_search.py

"""
Both binary search functions implemented below assume the element being searched
is an integer but this can certainly be done with strings as well.
"""

# Iterative Binary Search

def iterative_binary_search(arr: list, element: int) -> bool:
  start = 0
  end = len(arr) - 1
  
  while start <= end:
    mid = (end+start) // 2
    print(start, mid, end)
    if element == arr[mid]:
      return True
    elif element < arr[mid]:
      end = mid - 1
    else:
      start = mid + 1
  
  return False
  
  
 # Recursive Binary Search
 
def recursive_binary_search(arr: list, start: int, end: int, elem: int) -> bool:
  if start > end:
    return False
  mid = (end + start) // 2

  if elem == arr[mid]:
    return True
  elif elem < arr[mid]:
    end = mid - 1
    return recursive_binary_search(arr, start, end, elem)
  else:
    start = mid + 1
    return recursive_binary_search(arr, start, end, elem)