Improving Binary Search by Guessing
Improving Binary Search by Guessing

Improving Binary Search by Guessing

Published
2019-04-30


The following code (lightly modified from Hypothesis code for
clarity) is among the most useful things I have ever written:

def find_integer(f):
    """Finds a (hopefully large) integer n such that f(n) is True and f(n + 1)
    is False. Runs in O(log(n)).

    f(0) is assumed to be True and will not be checked. May not terminate unless
    f(n) is False for all sufficiently large n.
    """
    # We first do a linear scan over the small numbers and only start to do
    # anything intelligent if f(4) is true. This is because it's very hard to
    # win big when the result is small. If the result is 0 and we try 2 first
    # then we've done twice as much work as we needed to!
    for i in range(1, 5):
        if not f(i):
            return i - 1

    # We now know that f(4) is true. We want to find some number for which
    # f(n) is *not* true.
    # lo is the largest number for which we know that f(lo) is true.
    lo = 4

    # Exponential probe upwards until we find some value hi such that f(hi)
    # is not true. Subsequently we maintain the invariant that hi is the
    # smallest number for which we know that f(hi) is not true.
    hi = 5
    while f(hi):
        lo = hi
        hi *= 2

    # Now binary search until lo + 1 = hi. At that point we have f(lo) and not
    # f(lo + 1), as desired..
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if f(mid):
            lo = mid
        else:
            hi = mid
    return lo
This is loosely based on ideas from timsort.
The reason this code is so useful is that it lets you make many
operations adaptive at zero cost: If you have an operation that
it may be useful to do some large number of times, you can compose it
and do only \(O(\log(n))\) checks to do
\(O(n)\) work.
In particular the nice feature of this that justifies the term
adaptive is that the amount of work it does is logarithmic in the size
of the output. It either gives you a very large result or costs
very little.
An example of how this gets used in test-case reduction is the
following:
def reduction_pass(ls, predicate);
    ls = list(ls)
    i = 0
    while i < len(ls):
        # Will delete a sequence of length n in O(log(n))
        k = find_integer(lambda k: predicate(ls[:i] + ls[i + k:]))
        del ls[i:i + k]
        i += 1
This allows for a test-case reduction pass that never does
substantially more work than the naive greedy algorithm which tries
deleting one item at a time, but can potentially do very large deletions
with much less work than that when the opportunity arises.
A neat variant I realised earlier is that you can use this function
to define the following variant of binary search:
def binary_search_with_guess(f, lo, hi, guess=None):
    """Find n such that lo <= n < hi and f(lo) == f(n) != f(n + 1). It is
    assumed that f(hi) != f(lo) and will not be checked.

    ``guess`` is a prediction of the value of n and defaults to lo.
    This function runs in O(log(abs(guess - n))).
    """

    if guess is None:
        guess = lo

    assert lo <= guess < hi

    good = f(lo)

    if f(guess) == good:
        # Our guess was equivalent to lo, so we want to find some point after it.
        k = find_integer(lambda k: guess + k < hi and f(guess + k) == good)
        return guess + k
    else:
        # Our guess was equivalent to hi , so we want to find some point before it.
        k = find_integer(lambda k: guess - k >= lo and f(guess - k) != good)
        return guess - k - 1
This is a binary search with a twist, which is that you start with a
guess as to what you expect the answer to be. The cost of the
search is still logarithmic, but it’s logarithmic with respect to how
bad your guess is rather than how large the range of the search is. If
you can rely on your guess being pretty good, this will sometimes let
you do the binary search in \(O(1)\)
instead of \(O(\log(n))\).
Naturally this can’t improve on binary search (which is optimal) in
the general case, so how useful this is depends entirely on how good
your guess is. If your guess is maximally bad (i.e. you guess one end
and the correct answer was the other), this can make up to twice as many
calls to the test function as a classic binary search does, but as long
as your guesses are on average pretty good it will tend to win out.
The reason this came up for me was that I’m working on a variant of
Angluin’s
L* algorithm with the Rivest
and Schapire modifications. Without going into details, you have a
sequence of \(N\) elements. You know
the first one is good, and the last one is bad, and you want to find a
good element which is directly followed by a bad one, and so so using
binary search. You then make a change to your model that makes that bad
element good, but this can have an unknown knock-on effect on the other
elements, so you need to repeat the procedure. The use of the guess here
is this: Generally speaking, most elements are bad, and elements rarely
go from good to bad as a result of our fix procedure (it absolutely
can happen, it just usually doesn’t). This means that a pretty
reasonable guess is \(0\) on the first
iteration, and the element we just made good on the subsequent ones
(because the elements before it probably haven’t changed from good to
bad, and the element we just fixed is probably now good).
How much of an improvement this is would require more benchmarking
than I’ve done (i.e. anything other than eyeballing the times), but
anecdotally this guessing heuristic seems to be mostly very accurate, so
in theory it should be a factor of five to ten performance improvement
just based on the size of the examples (because it cuts out a \(\log(n)\) factor and the sequences are a
few hundred items long)..

