Sqrt(x)
Binary search the ANSWER, not the array
time O(log x)space O(1)
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.
Details
Animated on: x = 8 — compute floor(sqrt(x)) without using a built-in sqrt function.
Problem:Sqrt(x)Easy
Binary search the ANSWER, not the array
step 1 / 6
0
[0]1
[1]2
[2]3
[3]4
[4]5
[5]6
[6]7
[7]8
[8]Binary search the answer itself: floor(sqrt(8)) is somewhere between 0 and 8. Each guess m either squares too big or fits.
- low=0· arr[0] = 0
- high=8· arr[8] = 8
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
Every step in words
Show all 6 steps
- Binary search the answer itself: floor(sqrt(8)) is somewhere between 0 and 8. Each guess m either squares too big or fits.
- mid=4: 4^2=16 > 8. Too big — search smaller. high = 3.
- mid=1: 1^2=1 <= 8. This is a valid candidate (ans=1) — try a bigger mid. low = 2.
- mid=2: 2^2=4 <= 8. This is a valid candidate (ans=2) — try a bigger mid. low = 3.
- mid=3: 3^2=9 > 8. Too big — search smaller. high = 2.
- low has crossed high — the largest valid candidate found was 2. floor(sqrt(8)) = 2.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.