题目描述
求 x 的算术平方根，只保留整数部分（向下取整），x 是非负整数。
思路解析
最朴素的做法是从 0 往上枚举，算 1²、2²、3²…直到平方超过 x，停在前一个。能算对，但 x 很大时（比如十几亿）要试到几万次，太慢。
为什么能二分：候选答案 mid 越大，mid² 也越大，这是单调的。所以可以在区间 [0, x] 上对 mid 二分——若 mid² ≤ x，说明这个 mid 可行、还能往更大试（记下它，l 右移）；若 mid² 大于 x，说明 mid 太大（连同更大的都不行，r 左移）。这就把「逐个试」从 O(√x) 砍到 O(log x)。
准备 · 区间 [0,8]：把所有候选答案 0、1、…、8 排成一排（数组长度全程不变）。l=0、r=8 圈出搜索范围，答案 ans 先存 0。
第 1 次 · 取 mid：中间下标 mid = (0+8)//2 = 4。下一步用它的平方和 x 比大小。
第 1 次 · 判断 4² > 8：4² = 16，大于 8。说明 4 以及比 4 更大的候选都不可能是答案。这是负例：mid² 超了，要往小收。
第 1 次 · 收右 r=mid−1：mid² 太大，把 r 收到 mid−1 = 3，4 到 8 这半段（含 mid 本身）灰掉丢弃。ans 仍是 0，没更新。
第 2 次 · 取 mid：范围缩到 [0,3]。新的中间 mid = (0+3)//2 = 1，算 1²。
第 2 次 · 判断 1² ≤ 8：1² = 1，不超过 8。说明 1 是个可行答案，先把 ans 更新成 1，但可能还有更大的，继续往右试。
第 2 次 · 进左 l=mid+1：mid 可行，把它记进 ans=1，再把 l 推到 mid+1 = 2，去右半 [2,3] 找有没有更大的可行答案。左边 0、1 不必再看。
第 3 次 · 取 mid：范围 [2,3]，mid = (2+3)//2 = 2，算 2²。
第 3 次 · 判断 2² ≤ 8：2² = 4，仍不超过 8。又一个更大的可行答案，把 ans 更新成 2，再往右试。
第 3 次 · 进左 l=mid+1：ans 更新到 2，l 推到 3。现在 l 和 r 都指向 3，范围只剩一个候选。
第 4 次 · 取 mid：范围 [3,3]，mid = 3，算最后这个候选 3 的平方。
第 4 次 · 判断 3² > 8：3² = 9，大于 8，太大。又一个负例：r 收到 mid−1 = 2，ans 不更新。这一收，l(3) 越过了 r(2)，范围空了。
结束 · ans = 2：转折收尾：l 越过 r，循环结束。ans 停在最后一次满足 mid²≤x 的值 2，正是 √8 的整数部分。
不一定要在数组里二分——只要「答案越大越满足（或越不满足）」，就能直接在答案的取值范围里二分。爱吃香蕉的珂珂、分割数组的最大值都是这一招。
参考代码（Python）
1def mySqrt(self, x):
2 l, r, ans = 0, x, 0
3 while l <= r: # 注意等号
4 mid = (l + r) // 2
5 if mid * mid <= x: # 可行，记下并试更大
6 ans = mid
7 l = mid + 1
8 else:
9 r = mid - 1 # 太大，往小收
10 return ans复杂度分析
- 时间复杂度：O(log x) —— 每轮把候选范围砍一半，最多 log x 轮
- 空间复杂度：O(1) —— 只用 l、r、mid、ans 几个变量
套路模板
记住骨架：可行就记 ans 并往大走、不可行往小走。若求「最小可行」就反过来：可行时反而往小走。
1# 找「最大的满足 check 的值」
2l, r, ans = 最小, 最大, 默认值
3while l <= r:
4 mid = (l + r) // 2
5 if check(mid): # 可行
6 ans = mid; l = mid + 1 # 记录并往大走
7 else: r = mid - 1 # 不可行往小走
8return ans易错点
- 错误写法：循环结束直接 return l 或 mid → 正确写法：可行时显式 ans = mid，最后 return ans（退出时 l 已经越过答案（l=r+1=3），直接返回 l 会差一返成 3；显式记录最后一次可行的 mid 才稳）
- 错误写法：C++/Java 里写 mid * mid <= x → 正确写法：改成 mid <= x // mid（或用 long）（大数相乘 mid*mid 会溢出 int 变负数，判断翻车；Python 大整数无忧但其它语言必须防溢出）
- 错误写法：x = 0 或 1 时套公式出错 → 正确写法：令 l,r=0,x、ans=0 起，循环天然兼容（x=0 时区间 [0,0]、mid=0、0²≤0 记 ans=0 正确；硬塞特判反而易写错）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。