题目描述
思路解析
一句话答案：LeetCode 367 有效的完全平方数用二分查找：答案 x 落在 1 到 num 且越大平方越大，取 mid 比 mid×mid 与 num，相等即真、偏小抬 l、偏大压 r，时间 O(log n)、空间 O(1)。
判断 num 是不是完全平方数，到底在找什么数
给一个正整数 num，问有没有整数 x 满足 x×x=num，有就返回 true、没有返回 false，而且不许调用 sqrt 开方。题面 num=144 返回 true，12×12 正好是 144；num=14 返回 false，3²=9、4²=16，中间没有哪个整数平方等于 14。
从 1 挨个试到 num，会白算掉多长一截
逐个试值：让 x 从 1 数到 num，每个都平方看等不等于 num，等于就 true、否则 false。可 num 若接近 20 亿，最坏得试上十几亿次，时间 O(n)（n 是 num 的大小）。sqrt 又被禁用，挨个试根本走不动。
平方只增不减，半截候选可以整段跳过
关键在平方本身有序：x 越大，x×x 越大，绝不回头。把候选 x 从 1 排到 num，拿正中间的候选 mid 平方后和 num 比：mid×mid 比 num 小，mid 和它左边所有候选都够不着，左半连 mid 一起扔；比 num 大，右半全超了、一起扔。一比就砍掉一半候选，这就是二分查找，每轮砍半往剩下半边找。
取中点比完平方，该往哪半收、循环停在哪
用两个指针 l、r 圈住还没排除的候选，起点 l=1、r=num，两端都算数，是闭区间 [l,r]。每轮取中点 mid=(l+r)//2，算 sq=mid×mid 和 num 比：相等就返回 true；sq 偏小，x 在右边，l 抬到 mid+1；sq 偏大，x 在左边，r 压到 mid-1。收缩都要跨过 mid，留着已验过的它就缩不动。循环写 while l<=r，好让 l、r 撞到同一格时再比一次；l 越过 r 还没相等就返回 false。
num=144 逐轮列出 mid 和它的平方
起点 l=1、r=144。第一轮 mid=72，72×72=5184>144 偏大，r 压到 71。第二轮 mid=36，36×36=1296>144，r 到 35。第三轮 mid=18，18×18=324>144，r 到 17。第四轮 mid=9，9×9=81<144 偏小，l 抬到 10。第五轮 l=10、r=17，mid=13，13×13=169>144，r 到 12。第六轮 mid=11，11×11=121<144，l 抬到 12。第七轮 l=r=12，mid=12，12×12=144 相等，返回 true，七轮就从 [1,144] 逼到了 x=12。动画把范围缩到 1..14 演示，逼近道理一样。
mid×mid 冲破 int 上限，比较从此全反
每轮范围减半，最多约 log₂n 轮（n 是 num 大小），时间 O(log n)、空间 O(1)。最容易埋雷的是 mid×mid：num 接近 2³¹ 时平方冲破 32 位 int 上限、溢出成负数，本该偏大的判成偏小、方向反过来，得用 64 位 long 存 sq，或把比较改成 mid>num/mid 避开乘法。循环漏成 while l<r，l、r 撞到答案那格时直接跳出、少比一次，完全平方数会被误判成 false；偏小时只写 l=mid 不加 1，范围缩不动就死循环。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住三件事：mid×mid == num 就中了；偏小往右找（抬 l）；偏大往左找（压 r）。下面用 num=144 把每一轮砍半演给你看。
把候选答案 1 到 14 排成一排（格子里是候选值 x）。左指针 l 在最左、右指针 r 在最右，搜索范围就是它俩之间。
第 1 轮。在范围 [1, 14] 的正中间取出候选 x = 7（mid 指着它）。
把这个候选平方：7×7 = 49。接下来拿 49 跟目标 144 比大小。
比较这一对：49 < 144。平方还偏小。
49 比 144 小，说明 7 太小了，真正的 x 在它右边。把左指针抬到 mid 右边一格。
左指针 l 跳到下标 7（候选 8）。左边变灰的那些已被排除，搜索范围砍掉了一半。
第 2 轮。在范围 [8, 14] 的正中间取出候选 x = 11（mid 指着它）。
把这个候选平方：11×11 = 121。接下来拿 121 跟目标 144 比大小。
比较这一对：121 < 144。平方还偏小。
121 比 144 小，说明 11 太小了，真正的 x 在它右边。把左指针抬到 mid 右边一格。
左指针 l 跳到下标 11（候选 12）。左边变灰的那些已被排除，搜索范围砍掉了一半。
第 3 轮。在范围 [12, 14] 的正中间取出候选 x = 13（mid 指着它）。
把这个候选平方：13×13 = 169。接下来拿 169 跟目标 144 比大小。
比较这一对：169 > 144。平方偏大了。
169 比 144 大，说明 13 太大了，真正的 x 在它左边。把右指针压到 mid 左边一格。
右指针 r 退到下标 11（候选 12）。右边变灰的那些已被排除，搜索范围又砍掉一半。
第 4 轮。在范围 [12, 12] 的正中间取出候选 x = 12（mid 指着它）。
把这个候选平方：12×12 = 144。接下来拿 144 跟目标 144 比大小。
比较这一对：144 == 144。相等，命中！
正好相等！12 的平方就是 144，说明 144 是完全平方数，立刻返回 true。
二分查找在范围里精准命中了 x = 12。144 确实是完全平方数，最终答案 true。
三个高频追问：范围下界为何取 1、不用 sqrt 的替代解法、以及 mid×mid 的溢出处理。
参考代码
def isPerfectSquare(num): l, r = 1, num # 答案落在 1..num while l <= r: mid = (l + r) // 2 sq = mid * mid if sq == num: # 正好相等：找到了 return True elif sq < num: # 偏小：往右找 l = mid + 1 else: # 偏大：往左找 r = mid - 1 return False复杂度
- 时间：O(log n)，每轮把搜索范围砍一半，n 是 num 的大小，比从 1 试到 num 的 O(n) 快得多
- 空间：O(1)，只用 l、r、mid 几个变量，不开额外数组
易错点
面试追问把动画讲成自己的话
追问为什么搜索范围是 1 到 num，而不是 0 到 num？
追问不让用 sqrt，除了二分还有别的办法吗？
追问mid×mid 溢出怎么处理？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
猜数字大小
LeetCode 374 · 简单 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题