Problem Statement:
This problem is about finding the floor value of the square root of a non-negative integer x.
You cannot use built-in square root functions. The goal is to use binary search to compute the answer efficiently.
Approach:
- If
xis0or1, returnx. - Set the binary search range:
l = 2, r = floor(x / 2). - Use binary search to find the greatest number
msuch thatm * m ≤ x. - If
m * m === x, returnm. - If
m * m > x, search left side. - If
m * m < x, search right side. Returnras the floor square root.
Time & Space Complexity:
Time Complexity: O(logx)
Space Complexity: O(1)
Dry Run
Input: x = 8
Initial:
if (x < 2) → false (since 8 ≥ 2)
l = 2, r = Math.floor(8 / 2) = 4
Loop 1:
m = Math.floor((2 + 4) / 2) = 3
m * m = 9
8 < 9 → r = m - 1 = 2
Loop 2:
m = Math.floor((2 + 2) / 2) = 2
m * m = 4
8 > 4 → l = m + 1 = 3
Exit condition:
l = 3, r = 2 → l > r → loop ends
Return r = 2
var mySqrt = function(x) {
if (x < 2) return x;
let l = 2;
let r = Math.floor(x / 2);
while (l <= r) {
let m = Math.floor((l + r) / 2);
if (x === m * m) {
return m;
} else if (x < m * m) {
r = m - 1;
} else {
l = m + 1;
}
}
return r;
};
def mySqrt(x: int) -> int:
if x < 2:
return x
l, r = 2, x // 2
while l <= r:
m = (l + r) // 2
if m * m == x:
return m
elif m * m > x:
r = m - 1
else:
l = m + 1
return r
public class Solution {
public int mySqrt(int x) {
if (x < 2) return x;
int l = 2, r = x / 2;
while (l <= r) {
int m = l + (r - l) / 2;
long sq = (long)m * m;
if (sq == x) return m;
if (sq > x) r = m - 1;
else l = m + 1;
}
return r;
}
}
#include <iostream>
using namespace std;
int mySqrt(int x) {
if (x < 2) return x;
int l = 2, r = x / 2;
while (l <= r) {
int m = l + (r - l) / 2;
long long sq = 1LL * m * m;
if (sq == x) return m;
if (sq > x) r = m - 1;
else l = m + 1;
}
return r;
}
#include <stdio.h>
int mySqrt(int x) {
if (x < 2) return x;
int l = 2, r = x / 2;
while (l <= r) {
int m = l + (r - l) / 2;
long sq = (long)m * m;
if (sq == x) return m;
if (sq > x) r = m - 1;
else l = m + 1;
}
return r;
}
public class Solution {
public int MySqrt(int x) {
if (x < 2) return x;
int l = 2, r = x / 2;
while (l <= r) {
int m = l + (r - l) / 2;
long sq = (long)m * m;
if (sq == x) return m;
if (sq > x) r = m - 1;
else l = m + 1;
}
return r;
}
}
