Template: 5. BINARY SEARCH — Universal Template

5. BINARY SEARCH — Universal Template

# =============================================================================
# Use when: sorted data, monotonic condition, "minimum X such that..."
def binary_search(lo, hi, condition):
    """Finds the smallest value in [lo, hi] where condition(mid) is True."""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if condition(mid):
            hi = mid       # answer is mid or left
        else:
            lo = mid + 1   # answer is right
    return lo


# =============================================================================