How to Calculate the Square Root With Binary Search

A coworker recently challenged me to find an algorithm for calculating the square root of a number. I had no idea how to do it at first, but I realized I could use binary search, similar to the classic “number guessing” game.

To find the square root of a number n, I start with two pointers: lo (set to 0) and hi (set to n). In each iteration, I calculate a new guess as the average of lo and hi. I then square the guess and compare it to n. If the result is close enough to n (within a small precision), I return the guess. If it’s too high, I set the new upper bound hi to the guess. If it’s too low, I set the lower bound lo to the guess. This process repeats until the guess is accurate enough.

Here’s the code:

PRECISION = 1E-4

def sqrt(n: float) -> float:
    hi = n
    lo = 0
    while True:
        guess = (hi + lo) / 2
        result = guess * guess
        if -PRECISION < result - n < PRECISION:
            return guess
        if result > n:
            hi = guess
        else:
            lo = guess