京公网安备11010502063487号给定一个非负整数 x，计算并返回 x 的算术平方根向下取整的结果，不允许使用内置的指数或平方根函数。因为只要整数部分，可以用二分查找：找最大的整数 r，使得 r × r ≤ x。这道题最有价值的一点是整数溢出：直接写 mid * mid <= x，在 32 位整数里当 mid 大于 46340 时乘积会溢出，得到负数，比较结果就是错的。本文用真实的 Java 程序展示这个溢出，对比二分和牛顿迭代法需要的迭代次数，给出五种语言的实现，并把二分做成分步演示。
完整题目见官方页面（链接在文末）。x 最大是 2^31 - 1，也就是 2147483647，它的平方根是 46340.95…，取整是 46340。基准解是 Python 标准库的 math.isqrt，是精确的整数平方根。一共 18 组用例，覆盖：0、1、完全平方数、非完全平方数、以及两个端点 2147395599（比 46340² 小 1）、2147395600（就是 46340²）、2147395601、2147483647：
输入 [0] 输出 0 输入 [1] 输出 1 输入 [2] 输出 1 输入 [3] 输出 1 输入 [4] 输出 2 输入 [8] 输出 2
32 位有符号整数最大是 2147483647，46340² = 2147395600 还在范围内，而 46341² = 2147488281 已经超过了。对于 x = 2147483647，二分过程中如果 mid 取到 46341，mid * mid 在 Java 里溢出成了一个负数，mid * mid <= x 变成了真，mid 被当成了可行解。下面是真实运行的 Java 程序：
用 mid * mid 与 x 比较，在 32 位整数里会溢出： Java: 46341 * 46341 = -2147479015（真实值 2147488281，超过了 int 最大值 2147483647） Java: (mid * mid <= x) = true，而 46341 其实大于 x 的平方根 46340 Java: (mid <= x / mid) = false
Java 里 46341 * 46341 得到 -2147479015，用它和 x 比较得到 true，判断"46341 的平方不超过 x"，而事实是 46341 大于 x 的平方根 46340。把条件改写成 mid <= x / mid 就避开了乘法，结果是正确的 false。这也是本文五种语言的实现都使用除法比较的原因。Go 里的 int 是 64 位，JavaScript 的数字是双精度浮点，这两种语言里乘法不会溢出，但统一写成除法。
x 小于 2 时平方根就是它自己。否则平方根一定在 [1, x / 2] 里（x ≥ 2 时 x/2 不小于平方根）。在这个区间里二分：取中点 mid，如果 mid <= x / mid（即 mid * mid <= x，整数除法向下取整不影响这个等价关系），说明 mid 可能是答案，记下来，然后往右找更大的；否则往左。区间为空时，最后记下的 ans 就是最大的、平方不超过 x 的整数。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(x): if x < 2: # 0 和 1 的平方根就是它们自己 return x lo, hi = 1, x // 2 # x >= 2 时，平方根不会超过 x/2 ans = 1 while lo <= hi: mid = lo + (hi - lo) // 2 if mid <= x // mid: # 等价于 mid*mid <= x，但不会溢出 ans = mid # mid 可能就是答案，继续往右找更大的 lo = mid + 1 else: hi = mid - 1 return ans
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [0] → 0 [1] → 1 [2] → 1 [3] → 1 [4] → 2 [8] → 2
Java · 解法代码class Solution { public int mySqrt(int x) { if (x < 2) return x; // 0 和 1 的平方根就是它们自己 int lo = 1, hi = x / 2, ans = 1; // x >= 2 时，平方根不会超过 x/2 while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (mid <= x / mid) { // 等价于 mid*mid <= x，但不会溢出 ans = mid; // mid 可能就是答案，继续往右找更大的 lo = mid + 1; } else { hi = mid - 1; } } return ans; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [0] → 0 [1] → 1 [2] → 1 [3] → 1 [4] → 2 [8] → 2
Go · 解法代码func mySqrt(x int) int { if x < 2 { // 0 和 1 的平方根就是它们自己 return x } lo, hi, ans := 1, x/2, 1 // x >= 2 时，平方根不会超过 x/2 for lo <= hi { mid := lo + (hi-lo)/2 if mid <= x/mid { // 等价于 mid*mid <= x，但不会溢出 ans = mid // mid 可能就是答案，继续往右找更大的 lo = mid + 1 } else { hi = mid - 1 } } return ans }
$ go build -o bin . && ./bin < cases.jsonl [0] → 0 [1] → 1 [2] → 1 [3] → 1 [4] → 2 [8] → 2
JavaScript · 解法代码function mySqrt(x) { if (x < 2) return x; // 0 和 1 的平方根就是它们自己 let lo = 1, hi = Math.floor(x / 2), ans = 1; // x >= 2 时，平方根不会超过 x/2 while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); if (mid <= Math.floor(x / mid)) { // 等价于 mid*mid <= x，但不会溢出 ans = mid; // mid 可能就是答案，继续往右找更大的 lo = mid + 1; } else { hi = mid - 1; } } return ans; }
$ node run.js < cases.jsonl [0] → 0 [1] → 1 [2] → 1 [3] → 1 [4] → 2 [8] → 2
C++ · 解法代码using namespace std; class Solution { public: int mySqrt(int x) { if (x < 2) return x; // 0 和 1 的平方根就是它们自己 int lo = 1, hi = x / 2, ans = 1; // x >= 2 时，平方根不会超过 x/2 while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (mid <= x / mid) { // 等价于 mid*mid <= x，但不会溢出 ans = mid; // mid 可能就是答案，继续往右找更大的 lo = mid + 1; } else { hi = mid - 1; } } return ans; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [0] → 0 [1] → 1 [2] → 1 [3] → 1 [4] → 2 [8] → 2
共 18 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 18/18 Java 通过 18/18 Go 通过 18/18 JavaScript 通过 18/18 C++ 通过 18/18
牛顿迭代法：从 r = x 开始，反复令 r = (r + x // r) // 2，直到 r * r <= x。它每步把误差近似平方，收敛比二分快。我在 Python 里统计了两者所需的迭代次数（从 r = x 起步，牛顿法起点较差）：
牛顿迭代 r = (r + x // r) // 2 收敛所需的迭代次数（从 r = x 开始，直到不再变小）vs 二分的迭代次数： x= 10: 牛顿 2 次（结果 3），二分 2 次（结果 3），math.isqrt = 3 x= 1000: 牛顿 7 次（结果 31），二分 8 次（结果 31），math.isqrt = 31 x= 1000000: 牛顿 12 次（结果 1000），二分 19 次（结果 1000），math.isqrt = 1000 x=1000000000: 牛顿 18 次（结果 31622），二分 29 次（结果 31622），math.isqrt = 31622 x=2147483647: 牛顿 19 次（结果 46340），二分 30 次（结果 46340），math.isqrt = 46340
牛顿迭代次数在 x = 10 时是 2 次，x = 2147483647 时是 19 次；二分是 2 次和 30 次，二分每次把区间减半，需要约 log₂(x/2) 次。在这里牛顿法在大数上需要的迭代次数更少（19 次对 30 次），但每次迭代要做一次除法，两者的每步代价不同，所以这里的次数对比不等于耗时对比，我没有测耗时。两种做法的结果都与 math.isqrt 一致。
Python 版本另外和 math.isqrt 做了随机对拍：x 从 0 到 2^k - 1，k 取 3、8、16、31，覆盖不同的数量级：
随机对拍 50000 组（x 取 0 到 2^k-1（k 取 3、8、16、31）的随机整数），solve 与 brute 的结果全部一致。
另外四种语言只在上面 18 组固定用例上验证过，其中包含 32 位整数的上边界，没有做大规模随机对拍。
下面的演示用 x = 8。区间是 [1, 4]：mid = 2，2 × 2 = 4 ≤ 8，记下 ans = 2，往右 lo = 3；mid = 3，3 × 3 = 9 > 8，太大，往左 hi = 2；区间为空，答案是 2。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。