Automatically bisect a given function, without providing upper or lower bounds

autobisect.py

"""
Automatically bisect a given function, without providing upper or lower bounds.

The provided function is expected to:
-  take an integer as single argument
- be defined for all integers (positive and negative)
- return a truth value
- contain a single transition (either true to false or false to true)

The argument corresponding to the true value of the transition is returned.

The function is called about 3 times the bit-length of the result,
meaning the algorithmic complexity is O(log(result)).
"""


def autobisect(func):
    mini, maxi = 0, 1
    reference = bool(func(mini))

    while True:
        if bool(func(maxi)) != reference:
            break
        if bool(func(-maxi)) != reference:
            mini, maxi = -maxi, -mini
            reference = not reference
            break
        mini, maxi = maxi, 2 * maxi

    while mini + 1 != maxi:
        current = (maxi + mini) // 2
        if bool(func(current)) != reference:
            maxi = current
        else:
            mini = current

    return mini if reference else maxi


# Testing

import operator as op
from hypothesis import given, settings
from hypothesis.strategies import integers, sampled_from


@settings(max_examples=1000)
@given(integers(), sampled_from([op.ge, op.le]))
def test(threshold, operator):
    seen = []

    def func(x):
        seen.append(x)
        return operator(x, threshold)

    assert autobisect(func) == threshold
    assert len(set(seen)) == len(seen)
    bitlength = len(format(abs(threshold), "b"))
    assert 3 * bitlength - 2 <= len(seen) <= 3 * bitlength + 2