企业官网建设流程全解析

刷 LeetCode 的人应该都有印象，第 69 题“x 的平方根”算是二分查找和牛顿迭代的经典入门题。题面极短，就是让你实现一个函数，返回非负整数 x 的平方根，向下取整。直接调sqrt()当然能过，但那就失去意义了，面试官想看的是你手写算法的能力。网上这题的题解大多集中在二分法，讲牛顿迭代的也有，但很多只给个公式就完事了，没讲清楚为什么这么迭代、C 语言实现时有哪些精度和溢出上的坑。这篇文章把牛顿迭代法从头到尾拆开聊，从数学原理到 C 代码实现，再到我实际跑测试时踩过的几个问题，一次说清楚。

1. 拿到这道题，先别急着写代码

1.1 题目到底在问什么

先复述一下题目的核心要求：给定一个非负整数x，要求返回sqrt(x)的整数部分。比如x = 8，真实平方根约是2.82842，你要返回2。注意，不是四舍五入，是向下取整。

这里有个很容易忽略的点：输入x的范围。老版本题目里x是int，但 LeetCode 后来把范围调整过，实践中要考虑到x可能接近INT_MAX，也就是 2147483647 左右。这个细节直接影响了实现时的变量类型选择和溢出处理，后面会专门讲。

另一个容易出问题的地方是边界条件。x = 0时结果就是0，x = 1时结果是1。这两个值虽然简单，但如果你用的迭代公式或者二分边界没处理好，就会在这里出现死循环或者返回错误值。我见过不少人在x = 0上翻车，因为牛顿迭代的初始值直接取x，那分母就是 0，一下就出问题了。

这道题定位是“简单”级别，但它的价值在于两种标准解法——二分法和牛顿迭代法——都是高频面试考点。二分法思路直观，但边界条件考验人；牛顿迭代法代码更短，但需要你理解背后的数值分析原理，能讲清楚“为什么收敛”的人其实不多。

1.2 暴力解法为什么不行，二分法又是怎么回事

先说暴力解法。最天然的想法是从1到x逐个试，找到最大的i使得i * i <= x。时间复杂度是 O(√x)，比如x = 2147483647时，大约要试 46341 次。这个数字看着不大，但题目思路明显是要更优的方案，而且如果面试官追问大数据量场景，暴力解肯定不是他想要的。

二分法就优雅很多。核心思路是在[0, x]区间里找满足mid * mid <= x的最大mid。每次把区间缩小一半，时间复杂度 O(log x)，x到INT_MAX也只需要循环 31 次左右。

但二分法有个典型的坑：mid * mid可能溢出。如果mid是int，mid * mid在mid > 46340时就会超出int能表示的范围。这属于面试经典送命题，如果你能主动指出“这里要用long long防止溢出”，面试官对你的印象会好不少。

二分法虽然能过，但我个人觉得牛顿迭代法更值得花时间研究。原因是它背后是一整套数值计算的方法论，理解了牛顿迭代，你就等于掌握了一种“求方程近似根”的通用工具，以后遇到n次方根、n次方根的倒数、甚至一些更复杂的方程求根问题，都可以套同一个框架。这道题只是牛顿迭代最简单的应用场景。

2. 牛顿迭代法是怎么一回事

2.1 从切线逼近说起

牛顿迭代法也叫牛顿-拉弗森方法，核心思想非常直观：对于一个方程f(x) = 0，我们先猜一个近似解x₀，然后在函数曲线上找到(x₀, f(x₀))这个点，做一条切线，切线与 x 轴的交点就是新的近似解x₁。重复这个过程，近似解会越来越接近真实根。

把数学式子写出来。曲线在x₀处的切线斜率是f'(x₀)，切线方程为：

y - f(x₀) = f'(x₀)(x - x₀)

令y = 0，解得：

x₁ = x₀ - f(x₀) / f'(x₀)

这就是牛顿迭代的基本公式。

回到求平方根这个问题。我们要算sqrt(a)，等价于求方程f(x) = x² - a = 0的正根。把f(x)和它的导数f'(x) = 2x代入上面的公式，得到：

x₁ = x₀ - (x₀² - a) / (2x₀) = (x₀ + a / x₀) / 2

这就是求平方根的牛顿迭代公式。每次迭代，新的近似值等于“旧近似值”和“a 除以旧近似值”的平均数。

这个公式有个很有意思的直观理解：如果你猜的近似值偏小了，那么a / x₀就会偏大，两者的平均就会往真实值方向修正；反过来也一样。好比你要量一段绳子的长度，第一次估计短了，那么“总长除以估计值”就会偏大，取平均后新估计值就会更接近真实长度。这个“欠了就补、多了就拉回”的机制保证了迭代的稳定性。

2.2 收敛条件与初始值选择

牛顿迭代不是随便选个初始值就能收敛的，虽然平方根这种凸函数非常友好，但也有讲究。

先说初始值。理论上x₀ = a是一个简单的选择，对于a >= 1的情况，从a开始迭代一定能收敛到sqrt(a)，因为sqrt(a) <= a，而且函数在这个区间是凸的，迭代过程单调递减逼近真实值。但如果你偷懒把初始值设为x₀ = a，对于特别大的数，迭代次数会稍微多一点，不过也完全可接受。我在实际实现中喜欢用x₀ = a，最简单直接，逻辑不容易错。

再说收敛条件。理想的收敛条件当然是|x₁ - x₀| < ε，也就是两次迭代结果几乎没变化，说明已经逼近到了极限。但要注意，这里有个关键问题：我们最后要返回的是整数，所以精度其实不需要太高。你只要迭代到“新的迭代值”和“旧的迭代值”之间的差距小于 1，然后取较小的那个整数，答案就出来了。

有些题解里会用一个固定迭代次数，比如循环 10 次或者 100 次。这种做法不是不行，但不够优雅。因为需要的迭代次数跟初始值和目标精度有关，对这道题来说，从x₀ = a开始，double 精度下通常 6 到 8 次就收敛了，固定迭代 10 次确实够用。但更好的做法是动态判断收敛条件，既能保证正确性，又能减少不必要的计算。

这里还要提一个关键的数学性质：牛顿迭代法是二阶收敛的，也就是说每迭代一次，有效数字的位数大约翻一倍。第一次迭代可能只有 1 到 2 位有效数字，第二次就有 4 位，第三次 8 位，几次之后 double 的精度（大约 15 到 16 位十进制数字）就到顶了。这也是为什么固定迭代 5、6 次通常就够用的底层原因。

2.3 为什么这道题特别适合牛顿迭代

你可能要问，二分法已经很优秀了，为什么还要用牛顿迭代？两个原因。

第一，收敛速度。二分法每轮迭代只能把误差区间缩小一半，是线性收敛，需要大约 31 轮才能覆盖 31 位整数的范围。牛顿迭代是二阶收敛，误差平方级缩减。直观感受就是：二分法第一轮给你 1 位正确数字，第二轮 2 位，第三轮 3 位，近似线性增长；牛顿迭代第一轮给你 1 位，第二轮 2 位，第三轮 4 位，第四轮 8 位，是指数级增长。对这道题，二分法需要跑满约 17 轮（因为 2^17 = 131072，但实际最大输入 2^31 需要约 31 轮），牛顿迭代 5 到 6 轮就到天花板了。

第二，代码表达力。牛顿迭代法的核心公式x = (x + a / x) / 2一行代码就完成了迭代更新，整个循环体不超过 5 行。在面试场景中，代码越短越不容易出 bug，也越好跟面试官讲解。你还可以顺手展示一下自己对数值方法的理解，这比单纯背二分模板要有辨识度得多。

第三，可扩展性。理解了牛顿迭代之后，求立方根、求倒数（1/a）、求任意次方根都只是换一个函数和导数的事。同样是“求近似根”的问题，你会比别人多一套通用武器。

当然，牛顿迭代也不是银弹。如果函数有多个零点、初始值选得不好就可能收敛到错误的根；如果导数在某点趋近于 0，可能出现震荡甚至发散。这些是更进阶的坑，但在这道题里，目标函数是凸函数、导数严格为正（x > 0时2x > 0），所以完全不需要担心，初始值随便选正数都能收敛。

3. C 语言实现：从浮点到整数

3.1 第一版：浮点牛顿迭代

先上一个最直接的 C 语言实现，用double做迭代，最后把结果转成int：

#include <math.h> int mySqrt(int x) { if (x == 0) return 0; double x0 = x; double x1 = (x0 + x / x0) / 2.0; while (fabs(x1 - x0) >= 1e-7) { x0 = x1; x1 = (x0 + x / x0) / 2.0; } return (int)x1; }

注意几个细节。

x == 0单独处理，因为分母不能为 0。有人问x == 1需不需要单独处理，其实不处理也能得到正确结果：x0 = 1，x1 = (1 + 1/1) / 2 = 1，x1 - x0 = 0，循环直接跳过，返回(int)1 = 1。

收敛阈值1e-7怎么选？因为我们要返回的是整数，理论上只要误差小于 0.5 就能保证取整正确。但考虑到浮点运算本身有舍入误差，我会把阈值设得比 0.5 小几个数量级，比如1e-7。这样迭代出来的浮点值误差远小于 0.5，转成int后必然是正确的向下取整结果。

那能不能用1e-9或者更小？可以，但没必要。double的机器精度大约是2.2e-16，1e-9远大于它，完全可以达到。阈值设得太小，理论上没问题，但可能增加无意义的迭代次数。1e-7是个平衡点。

这个版本的代码逻辑清晰，容易理解，面试时先写出这一版，再逐步优化到整数版本，是很有条理的展示方式。

3.2 第二版：整数牛顿迭代

浮点版本虽然正确，但你可能注意到一个问题：我们用的是double运算，而题目要求返回int。既然题目要的是整数结果，有没有可能全程用整数运算，既避免浮点精度问题，又让代码更“C 味”十足？

完全可以。把迭代公式改造成整数形式：

int mySqrt(int x) { if (x == 0) return 0; int x0 = x; int x1 = (x0 + x / x0) / 2; while (x1 < x0) { x0 = x1; x1 = (x0 + x / x0) / 2; } return x0; }

这里的关键变化是收敛条件。浮点版本用|x1 - x0| < eps，整数版本没法用绝对误差，换成了一个很有意思的性质：当迭代值开始反弹、即x1 >= x0时，说明已经收敛到最小值了，直接返回x0。

为什么整数版会反弹？因为整数除法会截断小数部分，导致迭代过程中可能出现这样的情况：真实的浮点迭代值在逐渐收敛，但整数迭代值因为截断，在某一轮之后停止变化，或者出现微小波动。一旦x1 >= x0，就说明我们已经找到了最小的那个整数解，再迭代下去只会原地打转或者反弹回去。返回x0是正确且安全的。

为了验证这个实现的正确性，我在本机跑了一组测试，覆盖了几类典型输入：

实测全部通过。

但注意，这个版本有一个严重隐患：x / x0在 C 语言里是整数除法，要求x和x0都是整数，没问题。但如果x很大，x0也很大的时候，(x0 + x / x0)是否可能溢出int？我们来看最坏情况：x = 2147483647，x0 = 2147483647，x / x0 = 1，x0 + x / x0 = 2147483648，正好超出int范围（最大值 2147483647）——溢出，结果是未定义行为。这个问题在 LeetCode 上有时能通过（取决于编译器和平台），但绝对不能在生产代码里这么写。

3.3 溢出陷阱与代码演进

既然意识到了溢出的风险，就要把代码做成真正安全的版本。两个思路。

思路一：用long long。把x0和x1声明为long long，中间计算完全不担心溢出：

int mySqrt(int x) { if (x == 0) return 0; long long x0 = x; long long x1 = (x0 + x / x0) / 2; while (x1 < x0) { x0 = x1; x1 = (x0 + x / x0) / 2; } return (int)x0; }

long long在常见平台上至少是 64 位，最大值可达9.22e18，x最大才2.147e9，中间计算即使是x0 + x / x0也远不会溢出。这是最省事、最不容易错的方案。

思路二：纯int但避免中间加法溢出。这里有一个小巧思：不应计算x0 + x / x0，而是想办法避免这个加法超过INT_MAX。因为sqrt(x) <= 46341（当 x 最大时），迭代过程中x0会迅速降到这个量级，唯一可能溢出的是第一轮迭代：x0 = 2147483647，x / x0 = 1，加法溢出。

可以把第一轮的初始值改小，比如x0 = x / 2，这样第一轮x / x0 = 2，x0 + x / x0 <= 1073741824 + 2，远小于INT_MAX。但从x / 2开始迭代，收敛性依然有保证，因为sqrt(a) <= a / 2（当a >= 4），初始值大于真实根，迭代单调递降，依然收敛。

不过这个方案代码写起来要小心，而且需要额外分析初始值选择对收敛性的影响。我个人经验是：在工程上没必要为了省一个long long而引入复杂性，直接上long long是更稳妥的选择。但如果你能在面试时主动说出“用long long是因为要防止中间结果溢出”，就已经展示出了很好的工程意识。

最终版代码可以写成这样，既保证正确性，又控制代码量在 10 行以内：

int mySqrt(int x) { if (x == 0) return 0; long long x0 = x; long long x1 = (x0 + x / x0) / 2; while (x1 < x0) { x0 = x1; x1 = (x0 + x / x0) / 2; } return (int)x0; }

这个版本在 LeetCode 上实测能通过，运行时间也很稳定。如果遇到极端平台不支持long long（理论上不太可能在现代环境中出现），可以改用unsigned long long，效果一样。

4. 实际运行中的那些坑

4.1 精度问题：浮点版本为什么偶尔会返回错误答案

很多人用浮点版时，在x = 2147395600附近会翻车。这个数是46340 * 46340，正好是46340的平方，真实平方根就是精确的整数46340。浮点版本用double迭代时，因为舍入误差，最后算出的值可能是46339.999999999999或者46340.000000000001。如果转成int时是前者，就会得到46339，比正确答案小 1。

怎么解决？两个办法。

第一个办法是把收敛阈值调得更严格，比如1e-9甚至1e-12，让迭代结果更接近真实值，降低舍入误差造成的风险。但不绝对保险，因为 double 的精度上限就是约 16 位有效数字，你不可能消除所有误差。

第二个办法更实用：在返回前对结果做一个修正——检查(ans + 1) * (ans + 1) <= x是否成立，如果成立说明答案小了，补 1；再检查ans * ans > x是否成立（此时 ans 对应的ans * ans可能因溢出而需要用 long long），如果成立说明答案大了，减 1。这个“验证并修正”的思路在算法题里非常实用，相当于给结果加了一道保险。

相比之下，整数版的迭代过程天然规避了浮点误差，所以我才更加推荐整数版。只要你理解了反弹收敛条件，整数版几乎不需要额外修正。

4.2 死循环与溢出的现场

我一开始写整数版的时候，收敛条件用的是while (x1 != x0)，结果在x = 1时陷入了死循环。

为什么？当x0 = 2，x1 = (2 + 1 / 2) / 2 = (2 + 0) / 2 = 1，这时候x1 < x0，继续。x0 = 1，x1 = (1 + 1 / 1) / 2 = 1，这时x1 == x0。你可能会说，“相等了就跳出循环啊”，没错，所以循环条件应该是while (x1 != x0)，理论上会退出。但问题在于某些输入下，迭代会进入x1 = x0 + 1和x0 = x1 + 1的无限震荡，永远不相等。比如x = 2：

• x0 = 2, x1 = (2 + 2 / 2) / 2 = (2 + 1) / 2 = 1
• x0 = 1, x1 = (1 + 2 / 1) / 2 = (1 + 2) / 2 = 1（整数除法 3 / 2 = 1）

这里还算稳定，但换成更大的数，就可能出现两个值交替的情况。用x1 < x0作为循环条件就能保证退出：一旦x1 >= x0，说明迭代到头了，返回x0。

另外还有个小细节：我最早用int x0 = x时，在x = 2147483647的第一轮迭代就上溢了，结果陷入了循环。这就是 3.2 节提到的溢出问题，纯int版本在 LeetCode 上不一定每次都挂，但一旦算错，错误值可能引发连锁错误。后来统一用long long之后，所有边界测试都稳定通过了。

4.3 常见问题速查

这里整理一份我在学习和实际写代码过程中遇到的问题速查表，方便你对照排查：

有一个值得单独强调的点：无论你用哪个版本，(ans + 1) * (ans + 1)这个修正表达式本身也可能溢出。在 C 语言里ans是int，乘积也是int，如果ans = 46341（它本身是正确结果的候选），46341 * 46341远超int范围。所以校验时必须用long long：

if ((long long)(ans + 1) * (ans + 1) <= x) { ans++; } if ((long long)ans * ans > x) { ans--; }

这种“用更大类型做中间计算”的习惯，是写 C 代码的基本功。

4.4 关于 LeetCode 编译器的一点备注

有朋友问过，LeetCode 上跑 C 语言用的编译环境会不会影响结果。这个问题其实不大，LeetCode 对 C 语言的int基本都按 32 位处理，long long按 64 位处理，你的本地环境大概率也是同样行为。但要提醒一句，不要在本地用不同位数的实验性环境去验证这道题，比如在 16 位int的老式嵌入式编译环境里跑，结论会完全不同。

5. 从这道题延伸开去的想法

5.1 牛顿迭代和二分法的选择逻辑

面试时如果被问“这道题你打算怎么解”，我一般会分两步回答：先说二分法，因为它思路最简单、边界最好讲清楚，是保底方案；然后提一句“二分法时间复杂度 O(log x)，但如果想要更快收敛，也可以用牛顿迭代法，因为平方根函数的二阶收敛特性，通常只需要几次迭代就到 double 精度上限”。

面试官如果继续追问“牛顿迭代的原理是什么”，你就可以把切线逼近和迭代公式推导讲一遍。这个流程讲下来，既展示了基础算法能力，又体现了数值分析的理论功底。

从工程实践角度，二分法的优势是对收敛条件不敏感，代码不容易因输入变化而出现意外行为；牛顿迭代的优势是收敛快、代码短，但需要对数值计算的稳定性有一定认识。实际项目中如果只是偶尔求一次平方根，优先考虑可读性和稳定性；如果在循环体里高频调用且对性能有要求，牛顿迭代值得考虑。

5.2 扩展到其他根式与通用求根

这道题是理解牛顿迭代最好的跳板。拿求立方根举例，目标方程是f(x) = x³ - a = 0，迭代公式是x₁ = x₀ - (x₀³ - a) / (3x₀²) = (2x₀ + a / x₀²) / 3。代码只需要改一个表达式，其余逻辑几乎不变。

再比如说求某个数的倒数，不想用除法实现，可以用牛顿迭代求解方程f(x) = 1/x - a = 0，迭代公式为x₁ = x₀ * (2 - a * x₀)。这个形式看起来有点反直觉，但在一些没有硬件除法指令、或者除法代价极高的平台上，这是一个经典的软件实现技巧。

如果你在准备面试，我建议把这道题当作“牛顿迭代法”的入门练习题，再用它验证自己对浮点精度、整数溢出和收敛条件的理解。这三个点，每一个都能在面试中单独拿出来深挖，而这道题把它们全串起来了。

我个人在实际写题过程中的体会是：能写出二分法的人很多，能把牛顿迭代讲透的人很少。把原理、实现、边界、坑全部走一遍之后，你收获的远不止一道题的解，而是一套可以迁移到很多数值计算场景的方法论。最后再分享一个小习惯：我每次写完一个算法题，都会顺手把初始条件里的0、1、2、INT_MAX这四个值各跑一遍，十几秒的功夫，但能拦住绝大多数隐藏 bug。希望你也能把这个习惯带上。