x 的平方根 图解题解
求整数平方根不用从 1 逐个试——二分在 [0, x] 上找「平方不超过 x 的最大整数」，每步砍一半。
猜一个数的平方根就像猜数字：候选答案从 0 到 x 排一排，取中间 m 算 m×m——比 x 大说明 m 太大往左收，不超过 x 说明 m 可行就记下来、再往右探有没有更大的可行值。每次砍一半，而不是从 1 开始逐个试，把 O(√x) 压到 O(log x)。向下取整自然由「记可行值、继续往右」来保证。
这道题到底在问什么
- x
- 8
- 输出
- 2
先想最直接的笨办法
最朴素的做法，从 0 往上枚举，算 1 的平方、2 的平方、3 的平方，直到平方超过 x，停在前一个。能算对，但 x 很大时，比如二十亿，要试到四万多次，太慢。（动画第 3 步）
最优解：一步一步想明白
- 3最朴素的做法，从 0 往上枚举，算 1 的平方、2 的平方、3 的平方，直到平方超过 x，停在前一个。能算对，但 x 很大时，比如二十亿，要试到四万多次，太慢。
- 4为什么能二分：候选答案 m 越大，它的平方也越大，这是单调的。所以可以在区间 0 到 x 上对 m 二分。若 m×m 不超过 x，这个 m 可行、还能往更大试；若 m×m 超过 x，这个 m 太大、连同更大的都不行。一刀砍半，把逐个试从 O(√x) 降到 O(log x)。
- 5l＝0，r＝8，ans＝0把所有候选答案 0 到 8 排成一排，这排数全程不变。左指针 l 指 0、右指针 r 指 8，圈出搜索范围。答案 ans 先存 0。
- 6mid ＝ (0＋8)//2 ＝ 4取中间位置，mid 等于 0 加 8 除以 2，得 4。下一步用它的平方和 x 比大小。
- 716 大于 8 → 太大4 乘 4 等于 16，大于 8。说明 4 以及比 4 更大的候选，平方都超了，都不可能是答案。这是负例：往小收。
- 8r → 3，丢掉 4 到 8平方太大，把右指针 r 收到 mid 减 1，也就是 3。4 到 8 这半段，连同 mid 自己，灰掉丢弃。ans 仍是 0，没更新。
- 9mid ＝ (0＋3)//2 ＝ 1范围缩到 0 到 3。新的中点，mid 等于 0 加 3 除以 2，向下取整得 1。算 1 的平方。
- 101 不超过 8 → 可行，ans＝11 乘 1 等于 1，不超过 8。说明 1 是个可行答案，先把 ans 更新成 1。但右边可能还有更大的可行值，继续往右试。
- 11l → 2，ans＝1mid 可行，记进 ans 等于 1，再把左指针 l 推到 mid 加 1，也就是 2，去右半 2 到 3 找有没有更大的可行答案。左边 0、1 不必再看。
- 12mid ＝ (2＋3)//2 ＝ 2范围 2 到 3，中点 mid 等于 2 加 3 除以 2，向下取整得 2。算 2 的平方。
- 134 不超过 8 → 可行，ans＝22 乘 2 等于 4，仍不超过 8。又一个更大的可行答案，把 ans 更新成 2，再往右试。
- 14l → 3，ans＝2ans 更新到 2，左指针 l 推到 3。现在 l 和 r 都指向 3，范围只剩一个候选。
- 15mid ＝ (3＋3)//2 ＝ 3范围只剩 3 到 3，中点就是 3。算最后这个候选 3 的平方。
- 169 大于 8 → 太大，r → 23 乘 3 等于 9，大于 8，太大。又一个负例：r 收到 mid 减 1，也就是 2，ans 不更新。这一收，l 是 3 越过了 r 是 2，范围空了。
- 17l 越过 r，返回 ans＝2收尾：l 越过 r，循环结束。ans 停在最后一次满足平方不超过 x 的值，正是 2，也就是 √8 的整数部分。
- 18可行就记 ans 并右移，太大就左移把核心动作慢放一遍：每轮只做一件事，拿 mid 的平方和 x 比。不超 x 就把这个 mid 记进 ans 再往大找，超了就往小找。2 是最后一个被记下的可行值，定格在它。
- 21不一定要在数组里二分。只要答案越大越满足、或者越大越不满足，就能直接在答案的取值范围里二分。这一招叫二分答案。
- 23退出时 l＝3，但答案是 2亲眼看差一坑：循环退出时，左指针 l 已经冲到 3，但 3 的平方超了 x，不是答案。真正的答案 2 是被 ans 锁住的。所以一定返回 ans，不能返回 l。
- 27这题是二分答案的入门款：答案单调，就在答案范围上砍半。往上走，爱吃香蕉的珂珂、分割数组的最大值都是这一招。去二分专题用同一套骨架连着练，遇到卡点直接问小欧 AI 私教。
⚠️ 容易写错的地方
✗ 错：循环结束直接 return l 或 mid
✓ 对：可行时显式 ans ＝ mid，最后 return ans
退出时 l 已经越过答案，本例 l 变成 3，直接返回 l 会差一返成 3；显式记录最后一次可行的 mid 才稳
✗ 错：C++ / Java 里直接写 mid × mid
✓ 对：把乘积转成 long，或写成 mid ≤ x // mid
大数相乘会溢出 int 变负数，判断翻车；Python 大整数无忧，但其它语言必须防溢出
✗ 错：x 等于 0 或 1 时另写特判
✓ 对：令 l、r ＝ 0、x，ans ＝ 0 起，循环天然兼容
x 等于 0 时区间是 0 到 0、mid 是 0、0 的平方不超过 0、记 ans 等于 0 正确；硬塞特判反而易写错
完整代码（Python / C++ / Java）
Python
class Solution:
def mySqrt(self, x: int) -> int:
l, r = 0, x
ans = 0
while l <= r:
mid = (l + r) // 2
if mid * mid <= x:
ans = mid
l = mid + 1
else:
r = mid - 1
return ansC++
class Solution {
public:
int mySqrt(int x) {
int l = 0, r = x, ans = 0;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long long)mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
};Java
class Solution {
public int mySqrt(int x) {
int l = 0, r = x, ans = 0;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long) mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
}套路模板 · 二分答案求最大可行
# 找「最大的满足 check 的值」
l, r, ans = 最小, 最大, 默认值
while l <= r:
mid = l + (r - l) // 2
if check(mid): # 本题 check 是 mid*mid <= x
ans = mid # 记录可行解
l = mid + 1 # 还想要更大，往右
else:
r = mid - 1 # 不可行，往左
return ans// 找「最大的满足 check 的值」
int l = 最小, r = 最大, ans = 默认值;
while (l <= r) {
int mid = l + (r - l) / 2;
if (check(mid)) { // 本题: (long long)mid*mid <= x
ans = mid; // 记录可行解
l = mid + 1; // 往右找更大
} else {
r = mid - 1; // 往左
}
}
return ans;// 找「最大的满足 check 的值」
int l = 最小, r = 最大, ans = 默认值;
while (l <= r) {
int mid = l + (r - l) / 2;
if (check(mid)) { // 本题: (long)mid*mid <= x
ans = mid; // 记录可行解
l = mid + 1; // 往右找更大
} else {
r = mid - 1; // 往左
}
}
return ans;复杂度
时间复杂度
O(log x)
每轮把候选范围砍一半，砍到只剩一个最多 log x 刀
空间复杂度
O(1)
只用 l、r、mid、ans 这几个变量，不随 x 增长
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 x 的平方根 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
不用二分还能怎么做？+
牛顿迭代法。用 x 自身做初值，反复令 m 等于 m 加 x 除以 m 再除以 2，收敛极快，几步就到，但要小心整数取整和初值。面试能说出二分加牛顿两套即加分。
为什么 mid 写成 l 加 r 减 l 再除 2，而不是 l 加 r 除 2？+
l 加 r 在数很大时可能溢出 int。写成 l 加上 r 减 l 的一半，永远不超过 r，不会溢出。这是二分模板里的固定防溢出写法。
如果要保留小数怎么办？+
改成在实数上二分。把范围设成 0 到 x，按精度比如十的负六次方反复取中点逼近，或者用牛顿迭代在浮点上收敛。本题只要整数部分，所以闭区间整数二分就够。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。