Sqrt(x) — Right-Boundary Binary Search [LC 69, Google, Apple]

Problem Statement#

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

Constraints:

• 0 <= x <= 2^31 - 1

Example 1:

Input:  x = 4
Output: 2
Explanation: The square root of 4 is 2.

Example 2:

Input:  x = 8
Output: 2
Explanation: The square root of 8 is 2.828..., and since we round down, 2 is returned.

Example 3:

Input:  x = 0
Output: 0
Explanation: sqrt(0) = 0.

Why This Problem Matters#

Sqrt(x) (LC 69) is Google's favorite "easy" binary search problem — it consistently appears in phone screens and onsite rounds because it tests three things at once: recognizing that a math problem can be solved with binary search, handling the right-boundary template correctly, and reasoning about integer overflow in the squaring step.

The problem looks like pure math. Most candidates reach for Newton's method or a math library. But the intended solution is binary search on the answer space: "what is the largest integer k such that k * k <= x?" Once you frame it that way, you are searching a sorted implicit array ([0, 1, 2, ..., x]) for the rightmost value satisfying a condition. That is right-boundary binary search.

Right-boundary binary search — finding the last element satisfying a predicate — is the mirror image of left-boundary search. It appears in problems like "find the last position of a target" (LC 34), "maximum number of tasks assignable" (LC 2071), and "largest integer less than or equal to a given value." Mastering it here gives you the template for all of them.

The constraint x <= 2^31 - 1 also introduces a multiplication overflow hazard: mid * mid can exceed a 32-bit integer range. Knowing to use 64-bit arithmetic (or Python's unlimited integers) demonstrates production-ready thinking.

The Core Insight#

Reframe the problem: find the largest integer k in [0, x] such that k * k <= x.

The function f(k) = k * k is monotonically increasing. For small k the condition k * k <= x is true; for large k it becomes false. There is a single boundary — the last k where the condition holds — and that is the floor square root.

This is right-boundary binary search. The predicate is mid * mid <= x. When it is true, mid is a valid answer and we might do better by going right: lo = mid. When it is false, mid is too large: hi = mid - 1.

Because lo = mid (not lo = mid + 1) can cause an infinite loop when lo == hi - 1 (mid rounds down to lo, setting lo = lo and making no progress), we must use the upper-mid formula: mid = lo + (hi - lo + 1) // 2. This ensures mid rounds up, so when lo = mid, lo strictly increases.

The search range is [0, x], but we can tighten the upper bound. For x >= 1, the integer square root is at most x // 2 (because (x/2 + 1)^2 > x for all x >= 2). Tightening the bound from x to x // 2 halves the initial range, but does not change the asymptotic complexity.

Visual Dry Run#

Input: x = 14

Integer square root is 3 because 3*3 = 9 <= 14 but 4*4 = 16 > 14.

Input: x = 9

Common Mistakes#

1. Using lower-mid (lo + (hi - lo) // 2) with lo = mid. This causes an infinite loop when lo == hi - 1. The upper-mid formula lo + (hi - lo + 1) // 2 is required when the true branch sets lo = mid.

2. Integer overflow in mid * mid. For x = 2^31 - 1, mid can reach values around 46,340. 46,340^2 = 2,147,395,600 which is just under 2^31 - 1, but intermediate computations in the search may exceed that. In Java or C++, cast mid to long before squaring. In Python, this is never an issue.

3. Not handling x = 0 explicitly. With x = 0, lo = 0, hi = 0, the loop does not execute, and 0 is returned. This works correctly — but verify it by tracing the code.

4. Setting hi = x always. For large x, this works but starts binary search on a range of 2^31 values instead of a tighter bound. Setting hi = x // 2 (plus a special case for x < 2) halves the initial range. Mention this optimization to the interviewer.

5. Using the left-boundary template here. Left-boundary finds the first index where k*k >= x. Right-boundary finds the last index where k*k <= x. For floor square root, you want the last valid k, so the right-boundary template is correct.

6. Using floating-point square root and converting. int(math.sqrt(x)) works in practice but can be off by one due to floating-point rounding errors for large perfect squares. The binary search solution is exact.

7. Not handling x = 1 separately. hi = x // 2 = 0 with the tight bound, but sqrt(1) = 1, which is out of the search range. Special-case x < 2: return x when using the tight upper bound.

Solutions#

# Python — Sqrt(x) with right-boundary binary search (LC 69)
def mySqrt(x: int) -> int:
    if x < 2:                           # sqrt(0) = 0, sqrt(1) = 1: return directly
        return x
 
    lo, hi = 1, x // 2                 # floor(sqrt(x)) <= x//2 for all x >= 4
 
    while lo < hi:                      # loop until the range collapses to one value
        # upper-mid: rounds up so lo = mid always makes progress
        mid = lo + (hi - lo + 1) // 2
 
        if mid * mid <= x:              # mid is a valid square root candidate (could go higher)
            lo = mid                   # move lo UP — mid might not be the largest valid k
        else:                           # mid * mid > x: mid is too large
            hi = mid - 1               # discard mid and everything above it
 
    # lo == hi == largest k where k*k <= x
    return lo

// JavaScript — Sqrt(x) with right-boundary binary search (LC 69)
function mySqrt(x) {
    if (x < 2) return x;               // base cases: sqrt(0)=0, sqrt(1)=1
 
    let lo = 1;
    let hi = Math.floor(x / 2);        // floor(sqrt(x)) is at most x/2 for x >= 4
 
    while (lo < hi) {                   // loop until the single answer remains
        // upper-mid formula: rounds up so that lo = mid always strictly increases lo
        const mid = lo + Math.floor((hi - lo + 1) / 2);
 
        if (mid * mid <= x) {           // mid is valid: the true answer might be higher
            lo = mid;                  // raise the lower bound to mid
        } else {                        // mid * mid > x: mid is definitely too large
            hi = mid - 1;             // drop the upper bound below mid
        }
    }
 
    // lo === hi === floor(sqrt(x))
    return lo;
}

Complexity Analysis#

Binary search runs in O(log x) time. For x = 2^31 - 1, that is at most 31 iterations. Space is O(1).

Follow-up Questions#

Q: How does Newton's method compare? Newton's method: k = (k + x / k) / 2 starting from k = x. It converges quadratically (the number of correct digits doubles each iteration), so it is faster in practice. But it requires careful termination logic and floating-point awareness. Binary search is simpler and equally acceptable in interviews.

Q: How would you compute the integer cube root? Same approach: binary search for the largest k where k^3 <= x. Use the right-boundary template with predicate mid * mid * mid <= x.

Q: How would you check if x is a perfect square? After computing k = mySqrt(x), check if k * k == x. If yes, it is a perfect square. This is O(log x) total.

Q: Can you use this for arbitrary nth roots? Yes. Binary search [0, x] for the largest k where k^n <= x. For large n, use pow(mid, n) with overflow guards.

Q: Why is hi = x // 2 safe? For any x >= 4, floor(sqrt(x)) <= x // 2. Proof: (x/2)^2 = x^2/4 >= x iff x >= 4. So x // 2 is always an upper bound on the answer when x >= 4, and we handle x < 2 separately.

This Pattern Solves#

• LC 69 — Sqrt(x) (this problem)
• LC 34 — Find First and Last Position (right boundary part)
• LC 1539 — Kth Missing Positive Number
• LC 2071 — Maximum Number of Tasks You Can Assign
• LC 1482 — Minimum Number of Days to Make m Bouquets
• Any problem asking for the largest value satisfying a monotone condition

Key Takeaway#

Sqrt(x) is the canonical right-boundary binary search problem. The predicate is mid * mid <= x, and you want the largest mid where it holds. The right-boundary template uses lo = mid when the predicate is true, and hi = mid - 1 when false. Crucially, it pairs lo = mid with the upper-mid formula (lo + (hi - lo + 1) // 2) to prevent infinite loops — that + 1 inside the floor division is the single character that makes the right-boundary template work. Watch for integer overflow when computing mid * mid in statically typed languages.

Key Takeaways#

• LC 69 (Sqrt(x)) is the canonical right-boundary binary search problem asked frequently by Google and Apple in phone screens.
• Reframe sqrt as: find the largest integer k in [0, x] where k * k <= x — a monotone predicate perfectly suited for binary search.
• Right-boundary template: when the predicate is true, set lo = mid (not lo = mid + 1) because mid is a valid candidate.
• Pair lo = mid with the upper-mid formula lo + (hi - lo + 1) // 2 to guarantee progress and avoid infinite loops.
• In statically typed languages, cast mid to long before squaring to prevent 32-bit integer overflow for large inputs.
• Set hi = x // 2 (with a base case for x < 2) to halve the initial search range without changing asymptotic complexity.
• Use while lo < hi so the loop exits cleanly when lo == hi, returning the single surviving candidate as the answer.