Binary Search Using Python

Binary search is an efficient search algorithm that involves repeatedly dividing a list in half until the desired element is found or it is clear that the element is not present. It requires that the list be sorted beforehand. Here is an example of how to implement binary search in Python:

def binary_search(list, target):
  # Set the initial bounds of the search
  low = 0
  high = len(list) - 1
  
  # While there is at least one element remaining to be searched
  while low <= high:
    # Find the midpoint of the search bounds
    mid = (low + high) // 2
    # If the target is less than the element at the midpoint, search the left half
    if target < list[mid]:
      high = mid - 1
    # If the target is greater than the element at the midpoint, search the right half
    elif target > list[mid]:
      low = mid + 1
    # If the target is equal to the element at the midpoint, return the index
    else:
      return mid
  # If the target is not found after the search is complete, return -1
  return -1

# Test the function with a sample list and target
list = [1, 2, 3, 4, 5]
target = 3
index = binary_search(list, target)
print(index)  # Output: 2

This implementation of binary search has a time complexity of O(log n), meaning that the time it takes to run the search grows logarithmically with the size of the list. This makes it much more efficient than linear search for large lists. However, it requires that the list be sorted beforehand, which can add additional time complexity.

Using Recursion

def binary_search_recursive(list, target, low=0, high=None):
  # If the high index is not specified, set it to the length of the list minus 1
  if high is None:
    high = len(list) - 1
  
  # Base case: if the low index is greater than the high index, the target is not present
  if low > high:
    return -1
  
  # Find the midpoint of the search bounds
  mid = (low + high) // 2
  # If the target is less than the element at the midpoint, search the left half
  if target < list[mid]:
    return binary_search_recursive(list, target, low, mid-1)
  # If the target is greater than the element at the midpoint, search the right half
  elif target > list[mid]:
    return binary_search_recursive(list, target, mid+1, high)
  # If the target is equal to the element at the midpoint, return the index
  else:
    return mid

# Test the function with a sample list and target
list = [1, 2, 3, 4, 5]
target = 3
index = binary_search_recursive(list, target)
print(index)  # Output: 2

This implementation of binary search using recursion has the same time complexity as the iterative version: O(log n). It may be less efficient in practice due to the overhead of the recursive function calls. Like the iterative version, it requires that the list be sorted beforehand.