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.
Steps
- If
xis 0 or 1, 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. - Return
ras the floor square root.
Dry Run
Input: x = 4
- l = 2, r = 2 → m = 2
- 2 * 2 = 4 → return 2
Output: 2
Input: x = 8
- l = 2, r = 4 → m = 3 → 3*3 = 9 > 8 → r = 2
- l = 2, r = 2 → m = 2 → 2*2 = 4 < 8 → l = 3
- Loop ends → return r = 2
Output: 2
Time & Space Complexity
- Time Complexity: O(log x)
- Space Complexity: O(1)
/**
* @param {number} x
* @return {number}
*/
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;
};
#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;
}
}
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;
}
}
1 Comment
Well-written breakdown! I’m curious, though—how would you modify the solution for floating-point inputs with high precision? That’s often where the brute force or integer-only approaches fall short.