AlgoViz
HomeBinary Search

Find square root of a number

Medium

Binary search the answer, not the array

Problem

Given a positive integer n. Find and return its square root. If n is not a perfect square, then return the floor value of sqrt(n).

In simple words

Binary-search a number whose square is <= n — the biggest such number is the floor root.

The idea

The answer lies in 1..n and the predicate 'k*k <= n' is true up to a point and false after it, which is all binary search needs. Search that boolean boundary instead of scanning, and keep the last k that satisfied it.

The trick

  • Search the answer space — there is no array here at all.
  • Use 64-bit for k*k, or it overflows before the search finishes.
  • Keep the last valid k; the loop ends past it.
1
2
3
4
5
0
1
2
3
4

Step 1 of 7. Brute force: try 1, 2, 3, … until the square passes 28. Values: 1, 2, 3, 4, 5.

1/7
Brute force
timeO(√n)spaceO(1)

Count up.

1let k = 1;2while (k * k <= n) k++;3// k is now the first value whose square overshoots4return k - 1;

Input

array
[1, 2, 3, 4, 5]

Memory

k
—

Output

floor √
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
n = 36
Output:
6
Explanation:
6 x 6 = 36 exactly.

Example 2

Input:
n = 28
Output:
5
Explanation:
5x5=25 <= 28 < 36=6x6, so the floor is 5.

Example 3

Input:
n = 1
Output:
1
Explanation:
The square root of 1 is 1.

Constraints

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

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.