1. 问题背景与需求分析
计算一个非负整数的平方根是编程面试和算法练习中的经典问题。LeetCode第69题要求实现一个函数，给定非负整数x，返回x的平方根的整数部分（即向下取整）。例如，输入8，输出2，因为2.828...的整数部分是2。
这个问题的难点在于：
- 不能使用内置的平方根函数（如C语言的sqrt()）
- 需要在O(log n)时间复杂度内完成
- 必须处理大整数情况（如2^31-1）
2. 常见解法对比
2.1 暴力枚举法
最简单的思路是从0开始逐个尝试，直到找到最大的整数i满足i² ≤ x < (i+1)²。这种方法时间复杂度为O(√n)，对于大数效率太低。
2.2 二分查找法
利用平方根函数的单调性，在0到x之间进行二分查找。时间复杂度为O(log n)，是较好的通用解法。
2.3 牛顿迭代法
利用数学上的牛顿迭代公式，通过不断逼近的方法求得平方根的近似值。在计算机实现中，通常只需几次迭代就能达到很高精度。
3. 牛顿迭代法原理详解
3.1 数学基础
牛顿迭代法是一种求方程f(y)=0近似解的方法。对于平方根问题，我们希望求y² = x的解，即f(y) = y² - x = 0。
根据牛顿迭代公式：
y_{n+1} = y_n - f(y_n)/f'(y_n)
对于f(y) = y² - x，f'(y) = 2y，因此迭代公式简化为：
y_{n+1} = (y_n + x/y_n)/2
3.2 几何解释
这个公式可以理解为：在当前猜测点(y_n, y_n²)处作切线，切线与x轴的交点就是下一个猜测点y_{n+1}。随着迭代进行，猜测值会快速收敛到真实平方根。
4. C语言实现细节
4.1 基础实现
c复制int mySqrt(int x) {
if (x == 0) return 0;
double y = x; // 初始猜测值
double precision = 1e-6; // 精度控制
while (fabs(y * y - x) > precision) {
y = (y + x / y) / 2;
}
return (int)y;
}
4.2 整数优化版本
为了避免浮点数运算和精度问题，可以使用纯整数运算的变体：
c复制int mySqrt(int x) {
if (x < 2) return x;
int y = x / 2; // 初始猜测
while (y > x / y) { // 防止溢出
y = (y + x / y) / 2;
}
return y;
}
4.3 初始值选择技巧
初始猜测值的选择会影响收敛速度。常见策略：
- 对于小x，直接用x作为初始值
- 对于大x，用x/2作为初始值
- 更高级的方法可以使用位操作快速估计初始值
5. 边界条件与特殊处理
5.1 输入为0或1
这两个特殊情况可以直接返回输入值本身，避免不必要的计算。
5.2 大整数处理
当x接近INT_MAX时，需要注意：
- y*y可能溢出，应该改为比较y和x/y
- 初始猜测值不宜过大
5.3 终止条件优化
迭代何时停止是个关键问题：
- 浮点版本可以使用精度阈值
- 整数版本可以检查相邻两次迭代结果是否相同
6. 性能分析与实测
6.1 时间复杂度
牛顿迭代法的收敛速度是二次的，通常5-6次迭代就能达到很高精度。因此时间复杂度可以认为是O(1)。
6.2 实测对比
在x=2147395599（接近INT_MAX）时：
- 二分查找法需要约30次循环
- 牛顿迭代法只需要约10次循环
7. 常见问题与调试技巧
7.1 无限循环
可能原因：
- 终止条件设置不当
- 整数运算时y和x/y相等但不满足终止条件
解决方法： - 添加最大迭代次数限制
- 修改终止条件为|y_{n+1}-y_n|<1
7.2 结果不准确
可能原因：
- 整数运算的截断误差
- 初始猜测值太差
解决方法： - 最后检查y和y+1哪个更接近真实值
- 优化初始猜测策略
7.3 溢出问题
在计算y*y或x/y时可能溢出。防御性编程技巧：
- 使用long类型存储中间结果
- 改变比较方式（如用y > x/y代替y*y > x）
8. 扩展应用
牛顿迭代法不仅适用于平方根计算，还可以用于：
- 任意次方根计算
- 倒数计算
- 其他非线性方程求解
例如，计算立方根的迭代公式为：
y_{n+1} = (2y_n + x/(y_n*y_n))/3
9. 算法选择建议
在实际编程中：
- 对于通用情况，二分查找法更简单可靠
- 当需要高性能时，牛顿迭代法更优
- 在硬件加速环境中，可能有更优化的实现
在面试中，建议先实现二分查找法，再讨论牛顿迭代法作为优化方向。