The square root of n is the number r such that 
.
Square root computations are performed inside every pocket calculator,
but it is instructive to develop an efficient algorithm to compute square roots.
First, observe that the square root of 
must be at least
1 and at most n.
Let l=1 and r=n.
Consider the midpoint of this interval, m=(l+r)/2.
How does 
compare to n?
If 
, then the square root must be greater than m, so the
algorithm repeats with l=m.
If 
, then the square root must be less than m, so the
algorithm repeats with r=m.
Either way, we have halved the interval with only one comparison.
Therefore, after only 
rounds we will have identified the square root
to within 
.
This bisection method, as it is called in numerical analysis, can also be applied to the more general problem of finding the roots of an equation. We say that x is a root of the function f if f(x)=0. Suppose that we start with values l and r such that f(l) > 0 and f(r) < 0. If f is a continuous function, there must be a root between l and r. Depending upon the sign of f(m), where m=(l+r)/2, we can cut this window containing the root in half with each test and stop when our estimate becomes sufficiently accurate.
Root-finding algorithms that converge faster than binary search are known for both of these problems. Instead of always testing the midpoint of the interval, these algorithms interpolate to find a test point closer to the actual root. Still, binary search is simple, robust, and works as well as possible without additional information on the nature of the function to be computed.