What is binary search?

Binary search is an algorithm for finding an element in a sorted array or list that operates in logarithmic time O(log n). The idea is to compare the target value with the middle element of the current range at each step and discard half of the elements where the target is definitely not present.

Example in Python:

from typing import List, Optional

def binary_search(arr: List[int], target: int) -> Optional[int]:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return None

# Usage
arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 7))  # Will output index 3

It is important to note that binary search can only be applied to sorted data.