Bisection Search and the Perils of Floats

Exhaustive Enumeration and Approximate Solutions ended on a cost problem: marching through a grid one step at a time costs $O(\text{range}/\text{step})$ guesses, and tightening the tolerance $\epsilon$ multiplies that cost. Bisection search fixes this by discarding half the remaining search space on every guess instead of one grid point — a change that turns a cost linear in $1/\epsilon$ into one that is only logarithmic in $1/\epsilon$. This is the first genuinely fast algorithm in the vault, and it is also the first place a subtlety of float arithmetic bites: comparing floats for exact equality is unreliable, and every bisection search must be written around a tolerance, never around ==. This note builds bisection for approximate square roots, proves why it is dramatically faster than enumeration, and then details exactly how and why floating-point numbers fail to represent most real numbers exactly.

Learning objectives. By the end of this note you should be able to: