题目描述
思路解析
一句话答案：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 三个变量。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心一句：**二分找最大的数使它平方 ≤ x。mid² 太大就缩右、太小（没超）就探左边更大处，逼出整数平方根（向下取整）。**
范围用 l 和 r 圈定，灰格是已排除、再也不用看的候选。
候选正中间是 5，5²=25，还没超过 80。说明 5 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
把左半（含中点 5）灰掉，l 跳到 6，范围缩到 [6, 11]。注意 5 虽合格，但我们还想要更大的，所以也跨过它。
候选正中间是 8，8²=64，还没超过 80。说明 8 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
把左半（含中点 8）灰掉，l 跳到 9，范围缩到 [9, 11]。注意 8 虽合格，但我们还想要更大的，所以也跨过它。
候选正中间是 10，10²=100，已经超过 80 了。10 太大，它右边的数平方只会更大、更不行，所以整段右半（含 10）排除，往左缩。
把右半（含中点 10）灰掉，r 跳到 9，范围缩到 [9, 9]。
候选正中间是 9，9²=81，已经超过 80 了。9 太大，它右边的数平方只会更大、更不行，所以整段右半（含 9）排除，往左缩。
收缩后 r=8 小于 l=9，范围空了——二分结束，r 最后停在 8，它就是答案。
绿色格子就是答案 8：它的平方 64 没超 80，而再大一个 9 的平方 81 就超了。12 个候选只比了 4 次——O(log n)。
目标偏大时，mid² 往往还没超 x，于是不断丢左半、向右探更大的候选。
候选正中间是 5，5²=25，还没超过 120。说明 5 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
把左半（含中点 5）灰掉，l 跳到 6，范围缩到 [6, 11]。注意 5 虽合格，但我们还想要更大的，所以也跨过它。
候选正中间是 8，8²=64，还没超过 120。说明 8 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
把左半（含中点 8）灰掉，l 跳到 9，范围缩到 [9, 11]。注意 8 虽合格，但我们还想要更大的，所以也跨过它。
候选正中间是 10，10²=100，还没超过 120。说明 10 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
把左半（含中点 10）灰掉，l 跳到 11，范围缩到 [11, 11]。注意 10 虽合格，但我们还想要更大的，所以也跨过它。
候选正中间是 11，11²=121，已经超过 120 了。11 太大，它右边的数平方只会更大、更不行，所以整段右半（含 11）排除，往左缩。
收缩后 r=10 小于 l=11，范围空了——二分结束，r 最后停在 10，它就是答案。
绿色格子就是答案 10：它的平方 100 没超 120，而再大一个 11 的平方 121 就超了。12 个候选只比了 4 次——O(log n)。
答案在边界也不怕：只要轴的右端 ≥ 真实根，二分照样能停在正确位置。
候选正中间是 5，5²=25，还没超过 130。说明 5 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
把左半（含中点 5）灰掉，l 跳到 6，范围缩到 [6, 11]。注意 5 虽合格，但我们还想要更大的，所以也跨过它。
候选正中间是 8，8²=64，还没超过 130。说明 8 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
把左半（含中点 8）灰掉，l 跳到 9，范围缩到 [9, 11]。注意 8 虽合格，但我们还想要更大的，所以也跨过它。
候选正中间是 10，10²=100，还没超过 130。说明 10 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
把左半（含中点 10）灰掉，l 跳到 11，范围缩到 [11, 11]。注意 10 虽合格，但我们还想要更大的，所以也跨过它。
候选正中间是 11，11²=121，还没超过 130。说明 11 这个答案「够格」，但说不定更大的数平方也没超——所以往右边继续找更大的。
收缩后 l=12 超过 r=11，范围空了——二分结束，r 最后停在 11，它就是答案。
绿色格子就是答案 11：它的平方 121 没超 130，而再大一个 12 的平方 144 就超了。12 个候选只比了 4 次——O(log n)。
边界先想清：0 和 1 要能正确返回自身，超大 x 必须防溢出。
两个高频追问：单调性是二分前提、返回 r 的边界含义。
参考代码
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 停在向下取整的根复杂度
- 时间：O(log x)，候选范围 [0,x] 每比一次减半
- 空间：O(1)，只用 l、r、mid 三个变量
易错点
面试追问把动画讲成自己的话
追问为什么这道开方题可以用二分？
追问循环结束为什么返回 r 而不是 l？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题