方法1:二分查找
时间复杂度:$O(logN)$
空间复杂度:$O(1)$
解题思路
二分查找模板:
https://blog.csdn.net/See_Star/article/details/125441234
Java 代码
class Solution {
public int mySqrt(int x) {
int l = 0, r = x;
int res = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long)mid * mid <= x) {
res = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return res;
}
}