Sqrt(x): Binary Search for the Integer Square Root

Sqrt(x) is LeetCode 69, and it is one of the cleanest examples of binary search on the answer space. You are not searching through an array. You are searching through all candidate integers to find the largest one whose square is at most x. If you have seen the binary search pattern, this problem is a direct application of the search-for-boundary variant.

The problem

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. You must not use any built-in exponent function or operator.

• x = 4 returns 2, because sqrt(4) = 2 exactly.
• x = 8 returns 2, because sqrt(8) = 2.828... and you round down.

The answer space is the range of integers from 0 to x. For each candidate mid, you check whether mid * mid is at most x. The candidates that pass form a contiguous block on the left, and the ones that fail form a contiguous block on the right. You want the rightmost candidate that passes.

The approach: binary search on the answer space

The key observation is that the condition mid * mid is at most x is monotonic over the range [0, x]. Every candidate from 0 up to some value passes, and every candidate after that fails. That monotonic boundary is exactly what binary search finds efficiently.

The plan:

1. Set lo = 0 and hi = x.
2. Compute mid = lo + (hi - lo) // 2.
3. If mid * mid is at most x, then mid might be the answer or something larger might work too. Set lo = mid + 1.
4. If mid * mid is greater than x, then mid is too large. Set hi = mid - 1.
5. When lo > hi, return hi. It holds the largest value whose square fits.

Visual walkthrough: x = 8

The search space is [0, 8]. You are looking for the largest integer whose square is at most 8.

Four iterations to find the answer, even though the search space had 9 candidates. With larger values of x, the savings are dramatic. For x = 2,147,483,647 (the 32-bit integer max), binary search takes about 31 steps instead of two billion.

The code

Here is the complete Python solution for LeetCode 69:

def mySqrt(x):
    lo, hi = 0, x

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if mid * mid <= x:
            lo = mid + 1
        else:
            hi = mid - 1

    return hi

lo = 0, hi = x. The smallest possible square root is 0 (when x = 0). The largest possible is x itself (since for x of at least 1, sqrt(x) is at most x).

while lo is at most hi. You keep searching until the pointers cross. This is the standard form for finding the rightmost valid value.

if mid * mid is at most x: lo = mid + 1. The current mid fits, but a larger value might also fit. Move lo past mid to search right.

else: hi = mid - 1. The square of mid exceeds x. This candidate and everything larger is invalid. Move hi below mid.

Return hi. When the loop exits, lo has passed hi. The value hi is the last candidate where mid * mid was at most x.

Complexity analysis

Time: O(log x). Each iteration halves the search space. For x up to 2^31 - 1, that is at most 31 iterations.

Space: O(1). Just three variables: lo, hi, and mid.

Edge cases to watch for

• x = 0: The answer is 0. The loop body never executes because lo = 0 and hi = 0, so mid = 0, and 0 * 0 = 0 is at most 0. Then lo becomes 1, lo > hi, and you return hi = 0.
• x = 1: mid = 0 first, 0 * 0 = 0 fits, lo = 1. Then mid = 1, 1 * 1 = 1 fits, lo = 2. Now lo > hi, return hi = 1.
• Perfect square (e.g., x = 16): When mid = 4, 4 * 4 = 16 is at most 16, so lo moves to 5. The search continues, but 5 and above all fail. hi ends at 4. Correct.
• Large x and overflow: In Python, integers have arbitrary precision, so mid * mid never overflows. In languages like Java or C++, you should compare mid against x // mid instead of computing mid * mid to avoid integer overflow.

The building blocks

This problem is built from two reusable building blocks.

Binary search on the answer space. Instead of searching a sorted array, you search a range of candidate answers [0, x]. The condition mid * mid is at most x plays the role of the comparison. This is the same structural pattern used in Koko Eating Bananas, Split Array Largest Sum, and Capacity to Ship Packages.

Search-for-boundary pattern. You are not looking for an exact match. You are looking for the boundary between values that satisfy a condition and values that do not. Specifically, you want the rightmost value where the condition holds. The lo = mid + 1 / hi = mid - 1 template with a return of hi is the standard way to find this rightmost boundary.

# Rightmost boundary: find the largest mid where condition(mid) is true
lo, hi = lower_bound, upper_bound
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if condition(mid):
        lo = mid + 1
    else:
        hi = mid - 1
return hi

For Sqrt(x), condition(mid) is mid * mid is at most x. Plug it in and the problem is solved.

From understanding to recall

The logic here is simple: binary search a range, compare the square of the midpoint to x, narrow down. You probably see exactly how it works right now.

But picture yourself writing this in an interview in three weeks. Is it lo = mid + 1 or lo = mid? Do you return lo or hi? What are the initial bounds for hi? These details are small but they matter, and they are easy to mix up under pressure.

Spaced repetition fixes this. You type the solution from scratch today, again tomorrow, then in three days. After a few rounds, the boundary template and the return value are automatic. You do not rederive anything. You just write it.

Sqrt(x) is a perfect SRS candidate: the code is about 8 lines, the pattern transfers to harder problems, and the off-by-one decisions are exactly the kind of thing that trips people up when they have not drilled them.

Related posts

• Binary Search: More Than Finding a Number - The full binary search pattern guide, including the search-on-answer and search-for-boundary variants that Sqrt(x) is built on
• Koko Eating Bananas: Binary Search on the Answer - Another binary search on answer problem, this time finding the minimum valid speed rather than the maximum valid square root