Square Root of a Number

New·#69·Easy·Binary Search

Binary search the answer space, not an array

Asked at:AmazonGoogleMicrosoftAdobe

Practice mode

Step

Initialization

Binary search over candidate answers rather than over an array: low = 1, high = 28.

Recursion workspace

Binary Search on the Answer

Step 1 / 17init

100%

low

high

ans

Explanation

The answer must lie somewhere in 1…28, and squaring is increasing — so if mid² ≤ 28 every value below mid works too, and if mid² > 28 every value above fails. That monotonic split is what makes the answer space searchable.

step 1 / 17

Space play← → stepHome reset

TimeO(log n)·SpaceO(1)

Binary Search on the Answer

1function floorSqrt(n) {
2  let low = 1, high = n;//n: 28low: 1high: 28ans: 0
3 
4  // Binary search on the answer space
5  while (low <= high) {
6    const mid = low + Math.floor((high - low) / 2);
7    const val = mid * mid;
8 
9    // mid is small enough — look for a bigger one
10    if (val <= n) {
11      low = mid + 1;
12    }
13    // mid overshoots — look smaller
14    else {
15      high = mid - 1;
16    }
17  }
18 
19  // high ends on the largest value whose square fits
20  return high;
21}

n28

low1

high28

ans0

Command Palette

Square Root of a Number

Square Root of a Number