Warning: This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#69) before relying on it.
Home → Algorithms → Sqrt(x)

√ Sqrt(x)

An interactive visualization of how binary search finds the integer square root. Watch the algorithm narrow down the search space and compare squares step by step.

Binary Search LeetCode 69 ↗ Easy

The Problem

Given a non-negative integer x, return the square root of x, rounded down to the nearest integer (i.e., the floor value).

The returned integer should be non-negative. You must not use any built-in exponent function or operator (e.g., pow(x, 0.5) or x ** 0.5).

Interactive Visualization

Speed:
Binary Search Range
lo
1
hi
4
Square Area Visualization
Press Step to begin
Current Step
Press Step or Play to begin.
Code
fun mySqrt(x: Int): Int {    if (x < 2)        return x    var lo = 1; var hi = x / 2    while (lo <= hi) {        val mid = (lo + hi) / 2        val sq = mid.toLong() * mid        if (sq == x.toLong())            return mid        else if (sq < x)            lo = mid + 1        else            hi = mid - 1    }    return hi  // floor of sqrt}

How It Works

Key Insight

We need to find the largest integer mid such that mid * mid ≤ x. Since the function f(mid) = mid * mid is monotonically increasing, binary search is a natural fit: if mid² ≤ x, the answer is at least mid, so we search higher; if mid² > x, mid is too large, so we search lower.

The Algorithm

  • Base case: if x < 2, return x directly (sqrt(0) = 0, sqrt(1) = 1)
  • Search space: lo = 1, hi = x // 2 (for x ≥ 2, sqrt(x) ≤ x/2)
  • Each iteration: compute mid = (lo + hi) // 2 and sq = mid * mid
  • If sq == x: found an exact square root, return mid
  • If sq < x: mid might be the answer but could be larger → lo = mid + 1
  • If sq > x: mid is too large → hi = mid - 1
  • When lo > hi: the loop ends and hi holds the floor of the square root

Complexity

Time O(log x)
Space O(1)

Each binary search iteration halves the search space. We start with at most x / 2 candidates, so we need at most O(log x) iterations. Each iteration does O(1) work (one multiplication and comparison).