binary_search.py

from typing import List, Callable, TypeVar, Optional


T = TypeVar("T")


def binary_search(l: List[T], key: Callable[[T], int]) -> Optional[T]:
    """Perform a binary search.

    Arguments
    ---------
    l : List to be searched. Must be sorted. Should have O(1) element access in
        order for this function to be useful.
    key : Function to determine if an element is at, below, or above the
        target in the domain. Should return 0 when successfully found, an int
        less than 0 when below the target, and an int above zero when above the
        target.

    Returns
    -------
    The target if it is found. Otherwise returns None.
    """
    low = 0
    high = len(l) - 1

    while low <= high:
        mid = low + (high - low) // 2
        comparison = key(l[mid])

        if comparison == 0:
            return l[mid]
        elif comparison < 0:
            low = mid + 1
        else:
            high = mid - 1

    return None


foo = [{"a": 2, "b": 5}, {"a": 4, "b": 1}, {"a": 3, "b": 8}]
foo = sorted(foo, key=lambda x: x["a"])
target = {"a": 3, "b": -1}
result = binary_search(foo, key=lambda x: x["a"] - target["a"])