DSA Factory
Free lessonsBinary search · Stage 0 · Halving the search · Step 4

Search the answers

No list at all. Halve the range of possible answers instead. About 10 minutes.

The answers themselves are sorted

The whole square root of n is the largest r whose square is at most n. There is no list to search, but the possible answers 0, 1, 2, 3 and so on are in order. "Is r squared more than n?" goes no, no, no, then yes forever.

A question that flips once is all halving needs. Find the first r whose square passes n, then step back one.

The first too-big r: then step back one, and that is the answer.
Root of 40: which r is the first with r × r > 40?
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
lowhigh

Try 5: 5 × 5 = 25 is not more than 40. The first too-big r is later: low = 6.

Move 1 of 5

Pick a range that surely holds the answer

Here n is at most 10 to the power 15, and 32,000,000 times 32,000,000 is already more than that. So the first too-big r lies somewhere from 0 to 32,000,000.

Search that range with the same loop as before. Where it looked at a list entry, use the middle times itself.

0 to 32,000,000: covers every possible answer.
Use a long: in C++ and Java. The middle times itself can be far bigger than an int holds.
In code
answers = []
for n in nums:
    low, high = 0, 32_000_000
    while low < high:
        mid = (low + high) // 2
        if mid * mid > n:
            high = mid
        else:
            low = mid + 1
    answers.append(low - 1)
return answers
Quick check

You're finding the root of 30 and try mid = 6. 6 × 6 = 36. What next?

Searching for the first r with r × r > 30 · low = 4, high = 8
  1. Ahigh = mid
  2. Blow = mid + 1
  3. Chigh = mid − 1
Show the answer

high = mid. 36 is more than 30, so 6 is too big. But it might be the first too-big r, so keep it in range.

Your problem

Whole square roots

For each number n in nums, return its whole square root: the largest whole number r with r × r ≤ n. Don't use a built-in square root. Search for r instead.

Example
nums = [10, 16, 50] → [3, 4, 7]

1 ≤ count ≤ 200 · 0 ≤ each n ≤ 10^15 (use a long), so every root is below 32,000,000

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding