Square Root (x) Visualization & Animation

Finds the integer floor of √n without built-in functions using binary search on the answer space.

## What is it? Compute the integer square root of a non-negative integer `n` — the largest integer `x` such that `x² ≤ n` — without using any built-in square root function. Solved using binary search on the answer. ## How it works - Binary search over the range `[0, n]` - At each step, compute `mid = (low + high) / 2` - If `mid * mid == n` → return `mid` - If `mid * mid < n` → potential answer; store `mid`, search right half (`low = mid + 1`) - If `mid * mid > n` → search left half (`high = mid - 1`) - Return the stored answer ## When to use - "Binary search on the answer" pattern — when the answer space is monotone - Any problem asking for the floor/ceil of a derived value ## Key Points - Use `long` for `mid * mid` to avoid integer overflow for large `n` - O(log n) — search space halves each iteration - Pattern generalizes to: "find the largest x where f(x) is still valid"

Category: algorithms

Difficulty: beginner

Time Complexity: O(log n)

Space Complexity: O(1)

Square Root (x)

beginner

Finds the integer floor of √n without built-in functions using binary search on the answer space.

GFGLeetCode
PhaseInit
Mid—
Answer—
N =36— find floor(√36)
lo
mid
hi
1
1
[0]
2
4
[1]
3
9
[2]
4
16
[3]
5
25
[4]
6
36
[5]
7
49
[6]
8
64
[7]
9
81
[8]
top = i·bottom = i²
Current mid being tested
Valid answer / confirmed result
Active search space
Eliminated
Find floor(√36). Binary search on candidates 1..9. Each step tests mid² vs 36.