69. x 的平方根
题目描述
输入非负整数 x，求它的平方根，只保留整数部分，小数部分直接丢弃。
换句话说，返回满足 r * r <= x 的最大整数 r。
不能借助语言内置的幂运算或开方，例如 pow(x, 0.5)、x ** 0.5。
示例 1
输入：x = 4 输出：2
示例 2
输入：x = 8 输出：2
解释：8 的平方根约为 2.828，去掉小数后是 2。
数据范围
0 <= x <= 2^31 - 1
解题思路
答案是满足 mid*mid <= x 的最大 mid。这个条件对 mid 是单调的：小的都满足、大的都不满足，所以在 [0, x] 上二分。若 mid*mid <= x，mid 可能是答案，令 lo = mid；否则 mid 太大，令 hi = mid - 1。因为是 lo = mid，取中点必须向上取整 (lo+hi+1)//2，否则 lo+1 == hi 时会死循环。
为什么正确
答案始终在 [lo, hi] 内：lo*lo <= x，而大于 hi 的数平方都大于 x。
复杂度分析
时间 O(log x)，空间 O(1)。
易错点
mid*mid 在 C++/Java 中会溢出 int，要用 long；中点向下取整配合 lo = mid 会死循环。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def mySqrt(self, x: int) -> int:
lo, hi = 0, x
while lo < hi:
mid = (lo + hi + 1) // 2
if mid * mid <= x:
lo = mid
else:
hi = mid - 1
return loclass Solution {
public int mySqrt(int x) {
long lo = 0, hi = x;
while (lo < hi) {
long mid = (lo + hi + 1) / 2;
if (mid * mid <= x) {
lo = mid;
} else {
hi = mid - 1;
}
}
return (int) lo;
}
}class Solution {
public:
int mySqrt(int x) {
long long lo = 0, hi = x;
while (lo < hi) {
long long mid = (lo + hi + 1) / 2;
if (mid * mid <= x) {
lo = mid;
} else {
hi = mid - 1;
}
}
return (int)lo;
}
};func mySqrt(x int) int {
lo, hi := 0, x
for lo < hi {
mid := (lo + hi + 1) / 2
if mid*mid <= x {
lo = mid
} else {
hi = mid - 1
}
}
return lo
}var mySqrt = function(x) {
let lo = 0, hi = x;
while (lo < hi) {
const mid = Math.floor((lo + hi + 1) / 2);
if (mid * mid <= x) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
};function mySqrt(x: number): number {
let lo = 0, hi = x;
while (lo < hi) {
const mid = Math.floor((lo + hi + 1) / 2);
if (mid * mid <= x) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
}其他解法
二分查找思路直接、不易出错；牛顿迭代收敛更快、迭代次数更少，但需要一点数值分析的背景。
解法 2：牛顿迭代 时间 O(log x)，空间 O(1)
求 √x 等价于求 f(r)=r²-x 的正根。牛顿迭代从 r=x 开始，每一步用切线与 x 轴的交点更新，即 r ← (r + x/r) / 2。用整数除法时序列单调递减，一旦 r² ≤ x 就停止，此时的 r 恰好是 ⌊√x⌋。
收敛速度是二次的，靠近答案后每轮有效位数翻倍，实际迭代次数比二分少很多。需要理解牛顿法和整数版本的停止条件，C++/Java 中 r*r 要用 64 位整数防止溢出。
class Solution:
def mySqrt(self, x: int) -> int:
r = x
while r * r > x:
r = (r + x // r) // 2
return rclass Solution {
public int mySqrt(int x) {
long r = x;
while (r * r > x) {
r = (r + x / r) / 2;
}
return (int) r;
}
}class Solution {
public:
int mySqrt(int x) {
long long r = x;
while (r * r > x) {
r = (r + x / r) / 2;
}
return (int)r;
}
};func mySqrt(x int) int {
r := x
for r*r > x {
r = (r + x/r) / 2
}
return r
}var mySqrt = function(x) {
let r = x;
while (r * r > x) {
r = Math.floor((r + Math.floor(x / r)) / 2);
}
return r;
};function mySqrt(x: number): number {
let r = x;
while (r * r > x) {
r = Math.floor((r + Math.floor(x / r)) / 2);
}
return r;
}