the bisection method
Imagine you know that a hidden treasure is buried somewhere between two posts in a field, and you have a device that, at any spot, says only whether the treasure is to your left or to your right. You walk to the midpoint, ask the device, and throw away whichever half cannot contain it. Repeat, and the unsearched stretch shrinks by half every time. The bisection method finds a root of f(x) = 0 the same way: you keep halving an interval that is guaranteed to trap the root.
Concretely, you start with two points a and b where f(a) and f(b) have OPPOSITE signs (one negative, one positive). If f is continuous, the intermediate-value theorem promises a root somewhere between them. You compute the midpoint m = (a + b) / 2 and look at the sign of f(m). Whichever of [a, m] or [m, b] still has a sign change (opposite-sign endpoints) becomes the new interval; the other half is discarded. After n steps the interval has length (b - a) / 2^n, so the root is pinned to within that tolerance. To reach an error below epsilon you need about log2((b - a) / epsilon) steps — for example, shrinking from width 1 to 10^-6 takes about 20 evaluations.
Bisection is the tortoise of root-finding: it is GUARANTEED to converge (it cannot diverge or cycle), needs only the sign of f, and never the derivative. The price is speed — it converges only linearly, gaining a fixed factor of 1/2 per step, roughly one extra correct binary digit each iteration (about three steps per decimal digit). Faster methods like Newton or the secant method can leave it far behind once they are close to a root, which is exactly why robust solvers such as Brent's method use bisection as a safety net and switch to fast methods when it is safe.
Solve x^2 - 2 = 0 on [1, 2]. f(1) = -1, f(2) = 2, opposite signs. Midpoint 1.5 gives f = 0.25 > 0, so keep [1, 1.5]. Next midpoint 1.25 gives f = -0.4375 < 0, keep [1.25, 1.5]. The interval keeps halving toward sqrt(2) = 1.41421...; each step adds about one binary digit.
Each step halves the bracket — slow but utterly reliable.
Bisection needs a genuine sign change to start: if f only touches zero without crossing (a double root, like (x-1)^2), the two endpoints have the same sign and bisection cannot even begin. It also finds just one root inside the bracket, not all of them.