Pattern visualizer
Sqrt(x)
There's no array to search here, but the answer itself lives on a sorted number line: as a candidate m grows, m*m grows monotonically. That monotonicity is all binary search needs — treat every integer 0..x as a candidate answer and binary search for the largest one whose square doesn't overshoot x. Animated on: x = 8 — compute floor(sqrt(x)) without using a built-in sqrt function..
Binary search the ANSWER, not the array
time O(log x)space O(1)step 1 / 6
0
[0]1
[1]2
[2]3
[3]4
[4]5
[5]6
[6]7
[7]8
[8]line 2
Binary search the answer itself: floor(sqrt(8)) is somewhere between 0 and 8. Each guess m either squares too big or fits.
Pseudocode
1FUNCTION mySqrt(x):2 low = 0, high = x, ans = 03 WHILE low <= high:4 mid = (low + high) / 2, rounded down5 IF mid*mid <= x:6 ans = mid; low = mid + 1 (try bigger)7 ELSE:8 high = mid - 1 (too big)9 RETURN ans
← / → step · space play · Home restart