def bsearch(f, target, low, high):
    """ Given a function f(x), return the value x for which f(x) is closest to
    but does not exceed target. x is between low and high."""
    if abs(low - high) <= 1:
        if f(high) == target:
            return high
        return low
    low_value = f(low)
    high_value = f(high)
    middle = (low + high) // 2
    #print(f"f({low}) == {low_value}, f({high}) == {high_value}")
    if abs(low_value - target) < abs(high_value - target):
        return bsearch(f, target, low, middle)
    else:
        return bsearch(f, target, middle, high)