x 的平方根 图解题解
求整数平方根不用从 1 逐个试——二分在 [0, x] 上找「平方不超过 x 的最大整数」，每步砍一半。
猜一个数的平方根就像猜数字：候选答案从 0 到 x 排一排，取中间 m 算 m×m——比 x 大说明 m 太大往左收，不超过 x 说明 m 可行就记下来、再往右探有没有更大的可行值。每次砍一半，而不是从 1 开始逐个试，把 O(√x) 压到 O(log x)。向下取整自然由「记可行值、继续往右」来保证。
这道题到底在问什么
- 输入
- x = 4
- 输出
- 2 （2²=4）
- 输入
- x = 8
- 输出
- 2 （2²=4≤8<9=3²，取 2）
最优解：为什么这么做
一句话答案：LeetCode 69 x 的平方根：不直接开方，二分答案猜一个整数 m，用 m²≤x 判定再收缩范围，逼出平方还没超 x 的最大整数。mid 平方要防溢出，时间 O(log x)、空间 O(1)。
x 的平方根只要整数部分，到底求什么
给一个非负整数 x，返回它算术平方根的整数部分，小数全丢（向下取整，抹掉小数）。x=8 时 √8≈2.83，答案取 2；x=4 开得尽，答案 2。题目还压一条：不准用开方函数。翻过来，要找的其实是「平方还没超过 x 的最大整数」：它平方不超 x，再大一个就超了。
从 1 一个个平方试上去，x 一大慢在哪
x 最大能到约 20 亿（32 位整数上限），从 1 起把每个整数平方去撞 x、刚超过就停，最坏要撞四万多次（√20 亿≈46341）。这种沿答案从小往大挨个试是 O(√x)，x 一上亿就明显磨蹭。浪费在于：候选本排好序，却被逐个线性扫，顺序没用上。
平方随数只增不减，这队候选凭什么能二分
把 0 到 x 的整数排成一队当候选，数越大平方一路只增不减（这叫单调）。整队被劈成两段：靠前的平方没超 x（合格），靠后的超了 x（超标），交界处最后一个合格的数就是答案。合格与超标一旦翻面就翻不回来，这种有序结构正好能二分查找（候选一半一半地缩）。
只是这里不在现成数组里找值，而是二分答案：不直接算根，而是猜一个整数 m 用判定条件验证它行不行，再按结果把范围砍一半。
判定就一句 m²≤x，合格往右贪、超了往左缩
判定函数（判断猜的值行不行的规则）就一句 m²≤x：成立说明 m 合格、平方没顶到 x。范围 [l, r] 起手 l=0、r=x，每轮取中点 mid=l+(r-l)//2（这么写而非 (l+r)//2，防 l、r 相加溢出）。
若 mid²≤x，mid 合格，但更大的说不定也合格，就把左半连 mid 丢掉，l=mid+1 往右探更大的；若 mid²>x，mid 超标，右边平方只会更超，就 r=mid-1 往左缩。循环条件 l≤r，等 l 越过 r、范围空掉就停，此刻 r 就是那个最大整数——返回 r，不是 l。
拿题面 x=8，l、r、mid 每轮怎么跳
起手 l=0、r=8。第一轮 mid=0+(8-0)//2=4，4²=16>8，超标，r 缩到 3。第二轮 l=0、r=3，mid=1，1²=1≤8，合格，l 跳到 2。第三轮 l=2、r=3，mid=2，2²=4≤8，合格，l 跳到 3。第四轮 l=3、r=3，mid=3，3²=9>8，超标，r 缩到 2。此时 l=3 越过 r=2，范围空，循环停，返回 r=2，即 √8 的整数部分。
收口读 l 还是读 r，别抄反
循环停在 l>r 那刻，l 落在第一个超标的数、r 落在最后一个合格的数，答案要合格那个，返回 r；抄成返回 l 会比真答案大 1。另一处是溢出：x 接近 20 亿时 mid*mid 会冲破 32 位整数、乘出负数，判定全乱，Java、C++ 要把 mid 换成 long（Python 整数不限位无此患）。循环条件还得带等号 l≤r，漏了会跳过 l==r 那格，x=2 起就返回错值。
时间 O(log x)：范围 [0, x] 每比减半，20 亿也只约 31 次比较，比线性四万多次快几个数量级。空间 O(1)，只用 l、r、mid 三个变量。
▶ 动画逐步走查（共 31 步）——想跟着动画一帧帧对照就展开
- 3核心一句：**二分找最大的数使它平方 ≤ x。mid² 太大就缩右、太小（没超）就探左边更大处，逼出整数平方根（向下取整）。**
- 4范围用 l 和 r 圈定，灰格是已排除、再也不用看的候选。
- 5候选正中间是 5，5²=25，还没超过 80。说明 5 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
- 6把左半（含中点 5）灰掉，l 跳到 6，范围缩到 [6, 11]。注意 5 虽合格，但我们还想要更大的，所以也跨过它。
- 7候选正中间是 8，8²=64，还没超过 80。说明 8 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
- 8把左半（含中点 8）灰掉，l 跳到 9，范围缩到 [9, 11]。注意 8 虽合格，但我们还想要更大的，所以也跨过它。
- 9候选正中间是 10，10²=100，已经超过 80 了。10 太大，它右边的数平方只会更大、更不行，所以整段右半（含 10）排除，往左缩。
- 10把右半（含中点 10）灰掉，r 跳到 9，范围缩到 [9, 9]。
- 11候选正中间是 9，9²=81，已经超过 80 了。9 太大，它右边的数平方只会更大、更不行，所以整段右半（含 9）排除，往左缩。
- 12收缩后 r=8 小于 l=9，范围空了——二分结束，r 最后停在 8，它就是答案。
- 13绿色格子就是答案 8：它的平方 64 没超 80，而再大一个 9 的平方 81 就超了。12 个候选只比了 4 次——O(log n)。
- 14目标偏大时，mid² 往往还没超 x，于是不断丢左半、向右探更大的候选。
- 15候选正中间是 5，5²=25，还没超过 120。说明 5 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
- 16把左半（含中点 5）灰掉，l 跳到 6，范围缩到 [6, 11]。注意 5 虽合格，但我们还想要更大的，所以也跨过它。
- 17候选正中间是 8，8²=64，还没超过 120。说明 8 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
- 18把左半（含中点 8）灰掉，l 跳到 9，范围缩到 [9, 11]。注意 8 虽合格，但我们还想要更大的，所以也跨过它。
- 19候选正中间是 10，10²=100，还没超过 120。说明 10 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
- 20把左半（含中点 10）灰掉，l 跳到 11，范围缩到 [11, 11]。注意 10 虽合格，但我们还想要更大的，所以也跨过它。
- 21候选正中间是 11，11²=121，已经超过 120 了。11 太大，它右边的数平方只会更大、更不行，所以整段右半（含 11）排除，往左缩。
- 22收缩后 r=10 小于 l=11，范围空了——二分结束，r 最后停在 10，它就是答案。
- 23绿色格子就是答案 10：它的平方 100 没超 120，而再大一个 11 的平方 121 就超了。12 个候选只比了 4 次——O(log n)。
- 24答案在边界也不怕：只要轴的右端 ≥ 真实根，二分照样能停在正确位置。
- 25候选正中间是 5，5²=25，还没超过 130。说明 5 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
- 26把左半（含中点 5）灰掉，l 跳到 6，范围缩到 [6, 11]。注意 5 虽合格，但我们还想要更大的，所以也跨过它。
- 27候选正中间是 8，8²=64，还没超过 130。说明 8 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
- 28把左半（含中点 8）灰掉，l 跳到 9，范围缩到 [9, 11]。注意 8 虽合格，但我们还想要更大的，所以也跨过它。
- 29候选正中间是 10，10²=100，还没超过 130。说明 10 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
- 30把左半（含中点 10）灰掉，l 跳到 11，范围缩到 [11, 11]。注意 10 虽合格，但我们还想要更大的，所以也跨过它。
- 31候选正中间是 11，11²=121，还没超过 130。说明 11 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
- 32收缩后 l=12 超过 r=11，范围空了——二分结束，r 最后停在 11，它就是答案。
- 33绿色格子就是答案 11：它的平方 121 没超 130，而再大一个 12 的平方 144 就超了。12 个候选只比了 4 次——O(log n)。
⚠️ 容易写错的地方
✗ 错：int mid = ...; mid * mid
✓ 对：long mid = ...; mid * mid
x 接近 int 上限时 mid*mid 会整数溢出变负数，判断全错；Java/C++ 用 long
✗ 错：return l
✓ 对：return r
循环结束时 l 已越过答案一格（l=ans+1），停在答案上的是 r
✗ 错：while (l < r)
✓ 对：while (l <= r)
闭区间 [l,r] 下漏判 l==r 那一格，边界 x（如 0、1）会算错
完整代码（Python / C++ / Java）
Python
def mySqrt(x):
l, r = 0, x # 候选答案范围
while l <= r:
mid = l + (r - l) // 2
if mid * mid <= x:
l = mid + 1 # 还没超，往右探更大
else:
r = mid - 1 # 平方超了，往左缩
return r # r 停在向下取整的根C++
int mySqrt(int x){
long l = 0, r = x; // long 防 mid*mid 溢出
while(l <= r){
long mid = l + (r - l) / 2;
if(mid * mid <= x) l = mid + 1; // 还没超，往右
else r = mid - 1; // 超了，往左
}
return (int)r; // r 即向下取整的根
}Java
public int mySqrt(int x) {
long l = 0, r = x; // long 防 mid*mid 溢出
while (l <= r) {
long mid = l + (r - l) / 2;
if (mid * mid <= x) {
l = mid + 1; // 平方没超，往右探更大
} else {
r = mid - 1; // 平方超了，往左缩
}
}
return (int) r; // r 停在向下取整的平方根
}复杂度
时间
O(log x)
候选范围 [0,x] 每比一次减半
空间
O(1)
只用 l、r、mid 三个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 x 的平方根 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么最后返回的是 r 不是 l，它到底停在哪？+
循环在 l>r 时结束，之前 l、r 一直朝中间夹。合格的数（平方≤x）都落在左段，超标的都落在右段。收尾时 r 停在最后一个合格的数，l 停在第一个超标的数——答案要的是「平方不超 x 的最大整数」，正是 r。若返回 l 会取到第一个超标的数，比答案大 1。拿 x=8 验一下：结束时 r=2、l=3，返回 r=2 才对。
判定为什么用 m²≤x，不写成 m≤x/m？+
两种都在问 m 够不够格，但 m≤x/m 里的除法会惹麻烦：整数除法 x/m 直接抹掉小数，比较就不精确；换成浮点除法又可能因精度误差在边界上判错。m²≤x 全程只用整数乘法和比较，边界干净、结果确定。唯一代价是 m² 在 Java、C++ 这类定长整数里可能溢出，把 m 转成 long 就行，比处理除法的精度坑省心。
这题和在有序数组里二分查找一个数有什么不同？+
普通二分是数组已经摆在那儿，拿 mid 位置上的值和目标比，相等就找到。这题没有现成数组，是二分答案：候选是 0 到 x 的所有整数，没人告诉你哪个对，你猜一个 mid，用 m²≤x 这条判定条件验证它合不合格，再决定往左还是往右砍。共同点是都靠「单调有序」把范围每次砍一半，区别在一个比数组里的值、一个比自己现算的判定结果。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 x 的平方根 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。