69. x 的平方根
难度：简单 | 主题：二分查找——单调性判断
题目
给你一个非负整数 x，计算并返回 x 的算术平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。不允许使用任何内置指数函数和算符。
示例
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842...，返回整数部分 2
思路
先讲个故事：猜平方根
朋友说：“我想了一个数，它的平方不超过 100，你猜这个数最大是多少？”
你不会从 1 试到 10——你会猜 5，5² = 25 < 100；猜 8，8² = 64 < 100；猜 10，10² = 100，刚好。这就是二分查找平方根——在 [0, x] 中找最大的 m 使得 m² ≤ x。
引导式推导：从定义到二分
问题转化：求 sqrt(x) 的整数部分，等价于在 [0, x] 中找最后一个满足 mid * mid ≤ x 的数。
单调性：如果 mid * mid ≤ x，那么 mid 可能是答案，但更大的也可能满足，所以继续往右搜。
graph LR subgraph 在0到x中找ans A["猜ans=mid"] --> B{"mid² ≤ x ?"} B -->|Yes| C["可能小了<br/>left = mid+1"] B -->|No| D["太大了<br/>right = mid-1"] end C -->|循环结束| E["返回 right<br/>(最后一个合法值)"] D --> E
退出时为什么返回 right 不是 left？ 循环退出时 left = right + 1。left² 一定 > x，right² 一定 ≤ x。right 就是最后一个合法答案。
可以优化搜索范围
x ≥ 4 时 sqrt(x) ≤ x // 2。所以搜索范围可以缩小到 [1, x // 2]，减少一半。
graph LR A["x < 2"] -->|直接返回 x| B["0,1的平方根是自己"] A -->|x ≥ 2| C["搜索 [1, x//2]"]
代码
def mySqrt(self, x):
if x < 2:
return x
left, right = 1, x // 2
while left <= right:
mid = left + (right - left) // 2
if mid == x // mid:
return mid
elif mid < x // mid:
left = mid + 1
else:
right = mid - 1
return right
为什么用 mid == x // mid 代替 mid * mid == x？ 防止大数溢出。虽然 Python 不会溢出，但实践中写这个习惯在 C++/Java 实践中加分。
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(log x) | 二分范围 x |
| 空间 | O(1) | 几个变量 |
实战考量
频率分析
出现在：一面二分基础题，考察对二分边界的理解以及溢出处理意识。
延伸思考
Q：为什么返回 right 不是 left？
A：退出时 left = right + 1。left² 一定 > x，right² 一定 ≤ x。right 是最后一个满足条件的值。
Q：用牛顿迭代法怎么写？
A：r = (r + x / r) / 2，迭代到 r² 与 x 的差小于精度。收敛速度比二分快。
Q：如果要求精确到小数点后 k 位呢？
A：把范围放大 10^(2k) 倍，最后再缩小回去。或用牛顿法浮点迭代。
易错点
-
用除法防溢出
-
x < 2的特殊处理 -
返回
right不是left
生活类比
找平方根 → 找正方形边长
你知道一个正方形的面积是 10，想知道边长。你不会一个个平方算——二分猜边长：猜 3，面积 9 < 10；猜 4，面积 16 > 10。所以边长在 3~4 之间，整数部分是 3。
相关题目
| 题目 | 关系 |
|---|---|
| 50Pow(x,n) | 快速幂 |
| 704二分查找 | 二分基础 |
→ 返回题单：LeetCode学习路线图 > 八、二分查找
速记卡（面试闪卡）
Q1：一句话讲清「69. x 的平方根」到底是什么？
A：在 0 到 x 间二分，找平方不超过 x 的最大整数。
Q2：思路：二分找最后一个合法值 —— 怎么理解？
A：朋友让你猜平方不超过 100 的最大数：猜 5 太小、猜 10 刚好——这就是二分查找（Binary Search）。在 [0,x] 里不断夹逼，停在哪？落在右边界（Right Boundary）。
Q3：代码：除法防溢出 —— 怎么理解？
A：别用 mid*mid 怕溢出，改用 mid 与 x//mid 比大小，像用秤砣（Integer Division）比轻重；返回 right 不是 left，因为循环退出时 right 才是最后一个合法值。
Q4：复杂度：时间与空间 —— 怎么理解？
A：每次砍半，时间复杂度（Time Complexity）O(log x) 像折纸；只用了几个变量，空间复杂度（Space Complexity）O(1) 轻装上阵。
Q5：生活类比：猜正方形边长 —— 怎么理解？
A：已知面积 10 求边长，你不会挨个平方算——二分猜边长（Binary Search）：猜 3 面积 9、猜 4 面积 16，整数部分是 3。平方求根（Square Root）就是这么接地气。
Q6：核心速记主线有哪些？
-
二分找平方≤x最大数
-
用除法防整数溢出
-
返回 right 非 left
-
时间 O(logx) 空间 O(1)
口诀
A：平方求根二分搜，
除法防溢记心头。
右界保留莫遗漏，
logx 时间不用愁。