Sedgewick & Wayne · §4.2 Sorting and Searching

Inverting a Function with Bisection

Same trick as converting a number to binary — but now the number line is a curve. To solve Φ(x) = y for a monotone Φ, evaluate the midpoint, see whether it lands above or below the target height, and throw away the half of x that can't contain the answer.

Function Φ(x)

Questions to ask

Target y = Φ(x)

0.61

Question log

Press “Ask” to evaluate the first midpoint.

This is bisection: the same halving idea as before, generalized from integers to real numbers. It only needs Φ to be monotone — it never needs a formula for Φ^-1, which is exactly why it works for functions (like this logistic curve) that have no closed-form inverse.