Sqrt(x): Binary Search on the Answer, Not the Array

Sqrt(x) looks like a math problem, and that disguise is exactly why it's worth solving. There is no array anywhere in the prompt — yet the intended solution is binary search. The problem exists to teach one reframe: you can binary search over answers, not just over data structures. Once you see it, a whole family of "minimize the maximum" and "find the threshold" problems collapses into the same template.

Interviewers love this problem because it filters on reasoning, not memorization. Anyone can recite the binary search loop. The question is whether you can spot that the candidates 0, 1, 2, …, x form a sorted, searchable space — even though nobody handed you a sorted array.

The problem#

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

Two details in the statement shape everything that follows:

• You want the floor, not the exact root. Formally: the largest integer k such that k * k <= x. That phrase — largest value satisfying a condition — is the tell for the pattern.
• x can be as large as 2³¹ − 1, so any per-candidate scan needs to be cheap and the number of candidates you actually test needs to be small.

The brute force baseline#

Count upward until squaring overshoots, then step back one:

Correct, but the loop runs about √x times: for x = 2³¹ − 1 that's roughly 46,000 iterations. Not catastrophic — but it's linear in the size of the answer, and it completely ignores the structure of the problem. Every candidate you test tells you something about all the candidates on one side of it, and this loop throws that information away. State the O(√x) baseline in one sentence, then beat it.

The key insight: binary search the answer space#

Look at the predicate k * k <= x across every candidate k from 0 to x, with x = 8:

Squares only grow, so the predicate is monotonic: a run of true followed by a run of false, with a single boundary between them. The answer is the last true. That's the entire setup binary search needs — a sorted sequence isn't a property of arrays, it's a property of any monotonic predicate over an ordered range.

This pattern is called binary search on answer. Instead of searching an array for a target, you search the range of possible answers [0, x] for the boundary. Each probe at mid asks "is mid still a valid answer?" and eliminates half the range either way:

• mid * mid <= x → mid is valid, and so is everything below it. Record mid as the best answer so far, then search above it for something bigger.
• mid * mid > x → mid is too big, and so is everything above it. Search below.

Halving [0, x] repeatedly takes O(log x) probes — about 31 iterations for the worst-case input, versus 46,000 for the linear scan.

The optimal solution#

This is the exact algorithm the Sqrt(x) visualizer traces line by line:

Three choices here do all the work:

• answer accumulates the best valid candidate. In classic binary search you return the moment you find the target. Here there is no "target" — only a boundary — so every valid mid overwrites answer and the search keeps pushing right. When the loop ends, answer holds the last true.
• left = mid + 1 on success is the counterintuitive move. Finding a valid mid isn't the end; it's a floor. You want the largest valid value, so success means "go bigger".
• Bounds [0, x] handle the edges for free. For x = 0: mid = 0, 0 <= 0 passes, answer = 0. For x = 1: the loop tests 0 then 1, both pass, answer = 1. No special cases needed.

Walkthrough: x = 8#

Step 3 is the heart of the pattern: mid = 2 is valid, but the algorithm doesn't stop — it records 2 and probes higher, because 3 might also be valid. Step 4 proves it isn't (9 > 8), the window collapses, and the recorded answer = 2 is returned. Four probes instead of scanning three candidates one by one — and the gap widens fast: for x = 2³¹ − 1 it's ~31 probes versus ~46,000.

Complexity#

Binary search does a constant amount of work per iteration — one multiplication, one comparison, two pointer updates — and the range halves every time, so the iteration count is ⌈log₂(x)⌉. Space is three integers regardless of input size.

Common mistakes#

• Returning the first valid mid. mid * mid <= x being true doesn't mean mid is the answer — it means the answer is mid or larger. Record it and keep searching right. Returning early on x = 8 when mid = 1 gives 1 instead of 2.
• Integer overflow on mid * mid. In Java or C++ with 32-bit ints, mid can reach ~2³⁰ on the first probe and mid * mid silently overflows. Use a 64-bit long, or flip the comparison to mid <= x / mid (guarding mid != 0). JavaScript is safe here: near the decision boundary mid² stays below x < 2³¹, well inside exact double precision.
• Shrinking with right = mid instead of right = mid - 1. With the left <= right loop condition, keeping mid in the window means the window can stop shrinking — an infinite loop when left === right on a failing mid.
• Special-casing x = 0 and x = 1. Unnecessary, and a symptom of not trusting the invariant. Initializing answer = 0 and right = x makes both fall out of the loop naturally.
• Computing the root with floating point (Math.floor(Math.sqrt(x))-style logic re-derived via x ** 0.5). Besides being banned by the prompt, float rounding near huge perfect squares can land you one off — e.g. a result of 3.9999999 flooring to 3 when the true root is 4.

Where this pattern shows up next#

Sqrt(x) is the cleanest possible introduction to binary-search-on-answer, and the boundary-hunting loop transfers directly:

• Binary Search — the classic array version; same loop skeleton, target instead of boundary.
• Guess Number Higher or Lower — the predicate becomes an API call, but the halving logic is identical.
• First Bad Version — the purest boundary hunt: a run of good versions, then a run of bad ones, find the first bad. Sqrt(x) mirrored.
• Search in Rotated Sorted Array — binary search where deciding which half to keep takes real reasoning.

You can also step through it interactively and watch the left/right window collapse around the boundary probe by probe.

FAQ#

Why does binary search work for Sqrt(x) when there is no sorted array?#

Because binary search doesn't require an array — it requires a monotonic predicate over an ordered range. The candidates 0 through x are ordered, and the condition k * k <= x flips from true to false exactly once as k grows (squares are strictly increasing). That single true-to-false boundary is all binary search needs: each probe at mid tells you which side of the boundary you're on, letting you discard half the remaining candidates.

What is the time complexity of Sqrt(x) with binary search?#

O(log x) time and O(1) space. The search window starts as [0, x] and halves on every iteration, so it takes about ⌈log₂(x)⌉ probes — roughly 31 for the maximum 32-bit input. Each probe does constant work: one multiplication, one comparison, one pointer update. The linear-scan alternative is O(√x), about 46,000 iterations for the same input.

How do you avoid integer overflow when computing mid * mid?#

In languages with fixed-width integers (Java, C++, Go), compute the product in a 64-bit type — (long) mid * mid — or avoid the multiplication entirely by comparing mid <= x / mid with a guard for mid == 0. The overflow risk is real: the first probe sets mid near x/2, and squaring ~2³⁰ overflows a 32-bit int. In JavaScript this specific problem is safe because comparisons only matter near the boundary, where mid² < 2³¹ is exactly representable in a double.

Why does the algorithm keep searching after finding a mid whose square fits?#

Because a valid mid is a lower bound, not the answer. The problem asks for the largest integer whose square doesn't exceed x, so when mid * mid <= x succeeds, everything at mid and below is valid — but something bigger might be too. The solution records mid in answer and moves left past it. Only when the window empties do you know no larger candidate works, and the last recorded answer is the floor square root.

Is Newton's method better than binary search for integer square roots?#

Newton's method converges faster in practice (quadratically, roughly doubling correct digits per iteration) and is what many math libraries use internally. But for interviews, binary search on answer is the better choice: it's easier to prove correct, it has no floating-point subtleties, and it demonstrates a pattern that generalizes to dozens of other problems — Newton's method only computes roots. Both run comfortably within limits for 32-bit inputs.