x 的平方根
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个非负整数 x，计算并返回 x 的算术平方根。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5。
0 <= x <= 231 - 1
示例 1
2 × 2 = 4，整数部分为 2。示例 2
模拟答题者思考
1. 我先想暴力：从 0 开始逐个试 k，直到 (k+1)² > x，返回 k——最坏 O(√x)，在 x 接近 2³¹ 时太慢。
2. 重复在哪里？候选答案是一串升序整数 0,1,2,…，满足「k² ≤ x」的性质在 k 增大时从真变假——等价于找最大的 k 使 k² ≤ x，和有序数组上找边界一样适合二分。
3. 关键转化：在 [0, x]（或 [0, x//2]）上二分 mid：若 mid*mid ≤ x，说明 mid 可行且答案至少为 mid，记录 ans 并向右搜；否则 mid 太大，向左缩。
4. 例 x=8：mid=4 时 16>8 缩左；mid=2 时 4≤8 记 ans=2 再试更大；mid=3 时 9>8 结束，返回 2。
5. 乘法用 mid * mid 时注意 Python 无限精度；C++ 可用 (long long)mid * mid 防溢出。整体 O(log x) 次判定，空间 O(1)。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
l, r | int | 定义：待考察的「候选整数根」的左右边界，初始 l=0、r=x（x≥1 时可缩为 r=x//2）维护：真实答案（最大整数 ans 满足 ans² ≤ x）始终在 [l, r] 内更新：根据 mid² 与 x 比较，每轮排除约一半候选 |
mid | int | 定义：当前候选根 (l + r) // 2维护：将整数区间切成左段 [l, mid] 与右段 [mid+1, r]更新：若 mid² ≤ x 说明 mid 可行且可能还有更大根，记录 ans=mid 并令 l=mid+1；否则 r=mid-1 |
ans | int | 定义：目前为止找到的「最大整数根」，满足 ans² ≤ x维护：随二分推进单调不降；循环结束时即为题目要求的整数平方根 更新：每当 mid² ≤ x 时令 ans = mid |
落码步骤
1. 特判 x < 2 直接返回 x（0→0，1→1）
2. 初始化 l=2、r=x//2、ans=1
3. 当 l <= r：取 mid = (l + r) // 2
4. 若 mid * mid <= x：令 ans = mid，l = mid + 1（尝试更大的根）
5. 否则 r = mid - 1；循环结束返回 ans
代码实现
class Solution:
def mySqrt(self, x: int) -> int:
if x < 2:
return x
l, r = 2, x // 2
ans = 1
while l <= r:
mid = (l + r) // 2
if mid * mid <= x:
ans = mid # mid 可行，记录并往更大试
l = mid + 1
else:
r = mid - 1 # mid 太大
return ansclass Solution {
public:
int mySqrt(int x) {
if (x < 2) return x;
int l = 2, r = x / 2, ans = 1;
while (l <= r) {
long long mid = l + (r - l) / 2;
if (mid * mid <= x) {
ans = (int)mid; // mid 可行，记录并往更大试
l = (int)mid + 1;
} else {
r = (int)mid - 1; // mid 太大
}
}
return ans;
}
};
// 时间 O(log x)，空间 O(1)复杂度分析
O(log x)
O(1)
常见坑
C++ 中 mid * mid 用 int 相乘可能溢出，应转 long long 再比 x。
题目要的是整数部分（向下取整），不是四舍五入；x=8 应返回 2 而非 3。
二分写法要维护「最大可行 ans」并在 mid² ≤ x 时 l = mid + 1；若误用「找第一个 mid² > x」需记得返回 mid - 1，与本题语义一致但易写错边界。
必测边界 Case
0 → 0
x = 4 → 2
x = 8 → 2
x = 2147483647 → 46340（验证不溢出、不调用内置 pow）