A binary search based on bisect module

binary_search.py

import bisect
import itertools


def binary_search(f, lower=None, upper=None, precision=1):
    # Switch lower and upper
    if lower is None and upper is not None:
        return precision - binary_search(
            lambda x: not f(-x), -upper, None, precision)

    # Try zero as lower bound
    if lower is None and not f(0):
        return binary_search(f, 0, None, precision)

    # Find a negative lower bound
    if lower is None:
        powers = (2**x for x in itertools.count())
        lower = next(x for x in powers if not f(-x))
        upper = lower // 2
        return binary_search(f, -lower, -upper, precision)

    # Center the search
    if lower != 0:
        return lower + binary_search(
            lambda x: f(x + lower),
            lower=0,
            upper=None if upper is None else upper - lower,
            precision=precision)

    # Float conversion
    if precision != 1:
        return precision * binary_search(
            lambda x: f(x * precision),
            lower=0,
            upper=None if upper is None else int(upper / precision))

    # Find a positive upper bound
    if upper is None:
        powers = (2**x for x in itertools.count())
        upper = next(x for x in powers if f(x))
        lower = upper // 2
        return binary_search(f, lower, upper)

    # Lazy sequence
    class LazySequence:
        def __getitem__(self, x):
            return f(x)

    # Bisect
    return bisect.bisect_left(LazySequence(), True, lower, upper)


def test():
    from math import isclose

    # Find first integer for which the cube is greater than -10000
    i = binary_search(lambda x: x**3 >= -10000, upper=-4)
    assert i**3 >= -10000
    assert (i-1)**3 < -10000
    assert i == -21

    # Find first float for which the cube is greater than -10000
    i = binary_search(lambda x: x**3 >= -10000, upper=-4, precision=1e-3)
    assert i**3 >= -10000
    assert (i-1)**3 < -10000
    assert isclose(i, -21.544)

    # Find first float for which the cube is greater than -10000
    i = binary_search(lambda x: x**3 >= -10000, lower=-100, precision=1e-3)
    assert i**3 >= -10000
    assert (i-1)**3 < -10000
    assert isclose(i, -21.544)

    # Find first float for which the cube is greater than -10000
    i = binary_search(lambda x: x**3 >= -10000, precision=1e-3)
    assert i**3 >= -10000
    assert (i-1)**3 < -10000
    assert isclose(i, -21.544)

    # Find first float for which the cube is greater than 10000
    i = binary_search(lambda x: x**3 >= 10000, precision=1e-3)
    assert i**3 >= 10000
    assert (i-1)**3 < 10000
    assert isclose(i, 21.545)