def binary_search()

in util.py [0:0]

• 11 lines of code
• 4 McCabe index (conditional complexity)

def binary_search(func, constraint, minimum, maximum, tol=1e-5):
    """
    Performs binary search on monotonically increasing function `func` between
    `minimum` and `maximum` to find the maximum value for which the function's
    output satisfies the specified `constraint` (which is a binary function).
    Returns maximum value `x` at which `constraint(func(x))` is `True`.

    The function takes an optional parameter specifying the tolerance `tol`.
    """
    assert constraint(func(minimum)), "constraint on function must hold at minimum"

    # evaluate function at maximum:
    if constraint(func(maximum)):
        return maximum

    # perform the binary search:
    while maximum - minimum > tol:
        midpoint = (minimum + maximum) / 2.
        if constraint(func(midpoint)):
            minimum = midpoint
        else:
            maximum = midpoint

    # return value:
    return minimum