不用Math.sqrt判断完全平方数：二分查找、牛顿迭代与整数溢出陷阱

我当年第一次碰到“判断整数是否为完全平方数、但不能用 Math.sqrt”这种题时第一反应是那不是吃饱了撑的后来真在项目里被折腾了一回才明白这个限制有多实用。嵌入式设备上根本没有完整数学库某些性能敏感模块里每百万次调用能省下一个“开方”都是赚面试桌上考察的是你能不能跳出惯性思维而不是背 API。这篇文章把我在这个题目上踩过的坑、用过的方案完整梳理一遍。包括最暴力的循环试探、二分查找、牛顿迭代、数学预判以及在不同编程语言实现时的溢出陷阱。内容对考研复试、算法面试、嵌入式开发还有纯粹想搞懂原理的人都适用代码可以直接抄走。1. 为什么题目要把 Math.sqrt 禁掉1.1 完全平方数到底是什么完全平方数说白了就是某个整数 k 和自己相乘的结果即 n k²k 是非负整数。0 是 0 的平方所以 0 也算1 是 1 的平方也算4、9、16、25 都是。判断一个整数 n 是不是完全平方数等价于判断 sqrt(n) 是不是整数。这里有个容易忽视的点负数不算。因为任何整数的平方都是非负数所以判断之前先把负数排除掉这是所有实现里第一个要走的分支。1.2 直接开方的问题在哪说的直白一点平时用 Math.sqrt 判断完全平方数是“够用”的但不代表它“可靠”。先看浮点精度问题。在 JavaScript 里 0.1 0.2 不等于 0.3这是每个前端都背过的基础知识。Math.sqrt 返回一个浮点数对于大的完全平方数你开出来的是一个非常接近整数的浮点数但这个数未必能精确表示那个整数。你拿它再乘一次可能得到 n 附近的一个浮点数而不是精确的 n。const n 2147483649; // 2147483647^2 附近的一个数 console.log(Math.sqrt(n) * Math.sqrt(n) n); // 某些情况下会得到 false虽然语言和编译器会做很多优化但你在“完全平方数”这种精确性要求极高的场景里把结论建立在一个浮点数上本身就是有隐患的。再看工程场景。不是所有环境都给你提供了开方函数。我在一些低端单片机上做数据处理的时候math.h 里面很多东西是用软件模拟的一次 sqrt 调用可能要消耗几十个指令周期循环里去调用是灾难。还有一些场景是刻意不让你用比如算法面试题目就是想看你怎么在不调用库函数的情况下自己把问题解决掉。所以“不用 Math.sqrt”不是噱头而是一个很有现实意义的约束。2. 暴力尝试先从最容易想到的方案说起2.1 从 0 开始的暴力循环先说效率最低但最容易理解的办法从 0 开始往 n 的方向遍历逐个检查 i * i 是否等于 n。def is_square_brute(n: int) - bool: if n 0: return False i 0 while i * i n: if i * i n: return True i 1 return False这段代码没有任何技巧就是拿最原初的定义去套。好处是逻辑不容易出错特别适合在小范围数据上做验证。比如 n 25从 i 0 一直试到 i 5最后命中n 26则试到 i 6 时发现 36 26退出循环返回 False。2.2 暴力法的复杂度瓶颈问题也很明显循环次数和 n 的平方根成正比。n 是 10⁴ 时只要 100 次看起来还好n 是 10¹² 时就需要 10⁶ 次勉强能跑n 是 10¹⁸ 时要执行 10⁹ 次在大部分场景里已经没法接受了。复杂度是 O(√n)空间复杂度是 O(1)。作为讲解例子可以用但真用在生产环境里会被同事笑死。暴力法的价值在于它明确了“目标线”我们只是要找到一个整数 k使 k² n。查找一个整数自然就会想到二分法因为 k 的取值范围是单调递增的平方之后也是单调递增的完全符合二分查找的前提。3. 二分查找可靠且通用3.1 思路与迭代细节二分查找的原理不用多说在一个有序区间内掐头去尾每次缩一半。这里的“有序区间”就是整数平方根的候选范围。对于 n 2sqrt(n) 一定不会超过 n / 2甚至更紧凑。所以可以把搜索范围设成 [1, n / 2] 而不是 [0, n]。n 0 和 n 1 作为特例单独处理。每次取区间中点 mid计算 mid * mid 和 n 的关系相等说明 mid 就是平方根return Truemid * mid n说明平方根在右半边左边界收缩到 mid 1mid * mid n说明平方根在左半边右边界收缩到 mid - 1。有人会问为什么不用 mid (left right) / 2而要用 left (right - left) / 2。前者在 left right 很大时会溢出这在 C/C、Java 里是真实会踩到的坑。Python 因为整型不设上限所以没事但养成随手写后者这个习惯能少改很多 bug。3.2 一个可以直接抄的二分实现def is_perfect_square_binary(n: int) - bool: if n 0: return False if n 2: return True left, right 1, n // 2 while left right: mid left (right - left) // 2 square mid * mid if square n: return True elif square n: left mid 1 else: right mid - 1 return False用 n 16 走一遍left1, right8mid4square16直接返回 True。用 n 17 走一遍left1, right8mid4square16 17left 变成 5left5, right8mid6square36 17right 变成 5left5, right5mid5square25 17right4循环退出返回 False。过程清晰没有问题。复杂度是 O(log n)n 是 10¹⁸ 时也只需要大约 60 次循环比暴力法快了不知道多少个数量级。3.3 为什么 left mid 1 / right mid - 1我见过不少人写二分时循环体里更新边界习惯写成 left mid 或 right mid。这在某些变种问题里是正确的但在我们这个“判断是否存在使 mid² n”的问题里会导致死循环。原因是当 mid 不是答案时如果还把它留在区间内下一次仍然会重复检查这个 mid。比如 n 8left1, right4, mid22²48如果 leftmid则 left2right4下一次 mid33²98right3再下一次 mid2又回到刚才的状态永远停不下来。正确做法是每次把 mid 排除在区间外。因为 mid 已经检查过了不管它偏大还是偏小它都不可能是 sqrt(n) 的最终整数结果。这个细节是二分查找不出错的关键之一。4. 牛顿迭代法数学味的解法4.1 迭代公式怎么来的牛顿迭代的常规思路是解方程 f(x) x² - n 0。取一个初始值 x然后在 x 处做切线切线与坐标轴的交点比当前 x 更接近真实根。推导后得到迭代公式x_{k1} (x_k n / x_k) / 2这个公式直观上也很好理解如果 x_k 猜小了n / x_k 就偏大两者平均一下向中间靠拢如果 x_k 猜大了n / x_k 就偏小平均后同样往中间拉。对于完全平方数迭代会逐渐逼近那个整数根。对于非完全平方数迭代会停在平方根附近的某个整数上我们可以用最后一次的结果做验证。4.2 整数场景下的牛顿法实现算法里引入小数会比较麻烦尤其整数运算环境下我们希望全程使用整数。常见做法是把除法换成向下取整写成这样def isqrt_newton(n: int) - int: if n 0: raise ValueError(negative input) if n 2: return n x n y (x n // x) // 2 while y x: x y y (x n // x) // 2 return x def is_perfect_square_newton(n: int) - bool: if n 0: return False if n 2: return True root isqrt_newton(n) return root * root n注意点有两个。第一初始值 x n 是可以的甚至在 n 较大时也可以直接取 n // 2 1只要保证初始值不小于真实根即可第二停止条件是 y x说明迭代已经收敛连续两次的值不再下降这时候的 x 就是 floor(sqrt(n))。用 n 18 手工推一遍x 18y (18 1) // 2 99 18继续x 9y (9 2) // 2 5继续x 5y (5 3) // 2 4继续x 4y (4 4) // 2 4y x退出返回 x 44² 16 ≠ 18所以 18 不是完全平方数。整个过程只迭代了 4 次非常快。4.3 停止条件与坑牛顿法的坑集中在停止条件和除法细节上。使用整数除法时n // x 会把小数部分丢掉这会导致迭代序列和数学上的牛顿序列略有偏差。不过由于我们最后只需要得到 floor(sqrt(n))误差反而被“向下取整”给吸收掉了所以这种偏差是安全的。还有一点千万不要在循环里判断 x * x n 就返回。当 n 不是完全平方数时x 是向下取整的根x * x n确实不等于 n当 n 是完全平方数时x * x n 会成立。这个判断可以放在最后也可以放在循环里面但如果在循环里判断要注意不能因为某一步暂时满足就提前返回要确认 x 已经收敛到最终的整数根。我更喜欢统一放到最后逻辑更清晰。5. 数学预判把计算量前置削减5.1 末位数字筛选完全平方数的十进制末位只能是 0、1、4、5、6、9。也就是说如果一个整数末位是 2、3、7、8它不可能是完全平方数。这个判断成本极其低廉只需要一次取模就能拦截掉大约 40% 的候选数。代码里加一行if n % 10 in (2, 3, 7, 8): return False但要注意这一行只能“否定”不能“肯定”。末位是 1 的数不一定就是完全平方数比如 21、31、41 都不是。它是一个剪枝手段不是判定条件。5.2 模 16 筛选比末位数字更进一步的是模运算。所有完全平方数对 16 取模结果只可能是 0、1、4、9。验证起来不复杂。任意整数 k对 16 取模后是 0 到 15逐个算 k² mod 160 → 01 → 12 → 43 → 94 → 05 → 96 → 47 → 18 → 09 → 110 → 411 → 912 → 013 → 914 → 415 → 1确实只有 0、1、4、9 四种可能其余 12 种情况可以直接排除。也就是说模 16 预判能过滤掉大约 75% 的非完全平方数。5.3 预判与主算法怎么搭配预判的目的是降低主算法的调用次数适合“批量判断大量整数”的场景。例如你要生成某个区间内所有完全平方数或者过滤一批用户输入可以先做快速筛选再把可能成为完全平方数的少数数字送到二分或牛顿法里。组合起来的顺序大致是n 0 → Falsen % 16 不在 {0,1,4,9} → False再用二分查找或牛顿法做精确判定。实际操作中模 16 只能帮你减少后续计算量它本身也是 O(1) 的多花的时间几乎可以忽略。还要提醒一点如果你要判断的是单个数字这点优化可能感觉不出来但循环百万次的时候75% 的提前返回能让你明显看到耗时下降。6. 不同语言下的完整实现与陷阱6.1 Python大整数的天然优势Python 的 int 是任意精度乘法不会溢出写起来最省心。前面给出的二分和牛顿实现直接能用。真正在工程中Python 从 3.8 开始提供了 math.isqrt可以精确计算整数平方根。如果项目没禁止 math 库直接用 math.isqrt(n) ** 2 n 就行了。但题目既然规定不用 Math.sqrt我还是建议你手写至少一遍既锻炼思路也应对面试。6.2 JavaScriptNumber 精度要当心JavaScript 的 Number 是双精度浮点数超过 2^53 后整数精度就会出问题。用二分法时mid * mid 可能超出安全整数范围得到不准确的比较结果。普通整数范围内可以这样写function isPerfectSquare(n) { if (n 0) return false; if (n 2) return true; let left 1; let right Math.floor(n / 2); while (left right) { const mid left Math.floor((right - left) / 2); const square mid * mid; if (square n) return true; if (square n) left mid 1; else right mid - 1; } return false; }如果需要处理超大整数应该使用 BigIntfunction isPerfectSquareBigInt(n) { if (n 0n) return false; if (n 2n) return true; let left 1n; let right n / 2n; while (left right) { const mid left (right - left) / 2n; const square mid * mid; if (square n) return true; if (square n) left mid 1n; else right mid - 1n; } return false; }BigInt 的除法是直接截断取整正好符合二分查找中“中点取整”的需求但要注意语法里必须带 n 后缀不然会直接报类型错误。6.3 C/C / Java乘法的溢出问题C 语言里最经典的坑是 int 溢出。如果 n 本身是 intmid * mid 在 mid 稍大一点时就会突破 32 位整数的上限结果变成负数或魔改值比较就全乱了。所以至少要用 long long 或 unsigned long long 接收中间值。更稳妥的思路是避免乘法通过除法比较大小。下面这段 C 代码用 n / mid 和 n % mid 来做判断根正苗红#include stdbool.h bool isPerfectSquare(unsigned long long n) { if (n 2) return true; unsigned long long left 1; unsigned long long right n; while (left right) { unsigned long long mid left (right - left) / 2; unsigned long long quotient n / mid; unsigned long long remainder n % mid; if (quotient mid) { return remainder 0; } else if (quotient mid) { left mid 1; } else { right mid - 1; } } return false; }为什么 quotient mid 说明根在右边因为当 n / mid mid 时意味着 mid * mid n真实的 sqrt(n) 在 mid 右边反之则在左边。当 quotient mid 时如果 remainder 是 0说明 n 正好是 mid²如果 remainder 不是 0说明 n mid² r且 0 r mid此时 sqrt(n) 介于 mid 和 mid 1 之间肯定不是整数可以直接返回 false。这个写法规避了乘法溢出的问题代价是多做一次除法。但在二分查找只有几十次循环的情况下多几十次除法的开销几乎可以忽略。7. 我踩过的坑与排查清单7.1 负数和零负数不进判断直接返回 false这个大多数人能想到。容易漏的是 0 和 1。0 0²1 1²都是完全平方数。如果代码里把 right 设成 n / 2当 n 1 时 right 0left 1直接不进循环返回 false就错了。所以特例判断务必放在入口处。7.2 二分写成了死循环我的经验是判断二分写对没写对直接在脑子跑一个 n 2 的用例。n 2 不是平方数但能测试边界是否会正常收敛。left1, right1mid1平方小于 nleft2循环退出返回 false这没问题。但如果边界更新写成 left mid 这种就会永远卡在 left1, right1 上出不来。7.3 乘法溢出后假阳性我在一个 Java 面试题里写过 int 版本的平方判断结果输入 65536 这种稍大的数mid 到 256 左右时 mid * mid 65536没问题可一旦 N 接近 2^31int 直接爆炸出现负数逻辑彻底乱掉。排查方法很简单把 mid 的类型和返回中间变量的类型都调大到 long必要时用上面说的除法比较方式。7.4 排查清单速查表症状可能原因解决方案n0 或 n1 返回 false没有处理特例入口处判断 n 2 返回 true输入负数返回 true没有判断符号n 0 直接返回 false程序运行很久不结束二分边界没排除 mid更新为 left mid 1 / right mid - 1大数结果错误int 或 long 溢出换 long long / BigInt或改用除法比较JS 大于 2^53 数字错乱Number 精度上限改用 BigInt 实现C 语言对超大数误判mid * mid 溢出使用 n / mid 比较避免乘法8. 聊聊性能与真实工程取舍8.1 三种方案的时间对比我在本机用 Python 对 10 万个 1 到 10^12 之间的随机整数做了简单测试。暴力方案只测试了 1 到 10^6 的区间十万个数已经明显卡顿二分方案和牛顿方案在同一数据规模下耗时相差不大牛顿通常会快 20% 到 40% 左右因为它的迭代次数远少于二分的 log 次循环。如果加上模 16 预判随机输入场景下还能再快不少因为四分之三的数字在进入主算法之前就被筛掉了。这个数据不要太当真环境不同会有波动但趋势是稳定的越聪明的算法循环次数越少对数据规模越不敏感。8.2 项目里到底该选哪一种选型要看场景。如果只是判断少量整数哪一种都行我直接推荐二分查找因为代码短、思路直、不易出错。如果是嵌入式环境没有完整数学库并且 n 的范围确定推荐牛顿迭代配合模 16 预判性能好且代码固定。如果是处理超大整数比如 RSA 或者数论相关的工具Python 的 math.isqrt 或者自定义的“除法比较型二分”会更可靠避免浮点和溢出问题。如果是在面试现场我建议你先把二分的解法干净利落写出来然后再问一句“是否允许我使用牛顿迭代优化”这样既展示基础功又展示你对性能有感知。8.3 还能怎么扩展顺着这个题目可以延伸出很多变种判断一个整数是否是两个完全平方数之和在一个有序数组里找第一个平方数求一个任意大整数的整数平方根。核心思想都是“在不依赖浮点库的前提下利用整数运算构造确定性的数学过程”。我个人在实际操作中的习惯是写任何一行平方判断先确认数据范围会不会撑爆中间乘积再用除法退路方案保底最后再考虑要不要用预判来加速。这套顺序让我在多个语言里都能写出同一套稳定的 check 逻辑也少踩了不少隐形的坑。如果你也想彻底吃透这类题目建议把二分和牛顿两个版本各手写十遍直到不用大脑思考就能背出来为止。等到真正在项目里需要避开 Math.sqrt 的那一天你会感谢当时那个老老实实把循环和迭代推过一遍的自己。