如何实现整数平方根 sqrt(x)？（二分与牛顿迭代，LeetCode 69）

简化版

实现 mySqrt(x)：返回 x 的算术平方根向下取整的整数部分（如 sqrt(8) = 2）。不能用库函数。两种主流做法：① 二分查找——答案在 [0, x] 范围内，二分找「平方 ≤ x 的最大整数」，注意用 mid * mid 比较时防溢出（用 long 或除法）；② 牛顿迭代法——用切线逼近，迭代式 x_{k+1} = (x_k + x / x_k) / 2，收敛极快。

详细版

解法一：二分查找（推荐，思路清晰）

int mySqrt(int x) {
    if (x < 2) return x;                    // 0、1 直接返回
    long lo = 1, hi = x;
    while (lo <= hi) {
        long mid = lo + (hi - lo) / 2;
        if (mid * mid <= x) lo = mid + 1;   // mid 偏小，往右找更大的
        else hi = mid - 1;                  // mid 偏大，往左
    }
    return (int) hi;                        // hi 停在「平方 <= x 的最大整数」
}

解法二：牛顿迭代（收敛快）

int mySqrt(int x) {
    if (x < 2) return x;
    long r = x;
    while (r * r > x) {
        r = (r + x / r) / 2;                // 牛顿迭代逼近
    }
    return (int) r;
}

二分：在 [1, x] 找最大的 mid 使 mid*mid <= x，答案是循环结束时的 hi。
牛顿法：从 x 出发，r = (r + x/r)/2 不断逼近根，r*r <= x 时停。
溢出：mid * mid 可能超 int，用 long。
复杂度：二分 O(log x)，牛顿法 O(log x) 但常数更小（平方级收敛）。

完整版教学

一、题意：向下取整的整数平方根

求 x 的平方根并向下取整：sqrt(8) = 2.82… → 返回 2。等价于找最大的整数 k，使得 k² ≤ x。这是个「在单调条件上找边界」的问题——k² 随 k 单调递增，所以能用二分；也可以用牛顿迭代这种数值逼近法。

二、解法一：二分查找

因为 k² 关于 k 单调递增，可以在 [0, x] 范围二分找答案：

取中点 mid，比较 mid² 和 x：
- mid² <= x：mid 可能是答案，但也许还能更大 → lo = mid + 1（往右找更大的可行值）。
- mid² > x：mid 太大 → hi = mid - 1（往左）。
循环 lo <= hi 结束时，hi 恰好停在「平方 ≤ x 的最大整数」（因为每次 mid²<=x 时把 lo 推过 mid，最后 hi 落在最后一个满足的位置）。返回 hi。

这是「二分查找右边界」的经典模板，理解「返回 hi」是关键。

三、防溢出：mid * mid 的坑

mid 可能接近 √(2³¹) ≈ 46340，mid * mid 在 mid 较大时会超过 int 范围溢出成负数，导致比较出错。两种解法：

用 long 做乘法：long mid，mid * mid <= x，long 范围足够。（推荐）
改用除法比较：mid <= x / mid，避免乘法溢出，但要注意整除的精度。

面试里忘记处理 mid*mid 溢出是高频扣分点，务必用 long 或除法。

四、解法二：牛顿迭代法

牛顿法是求方程根的通用数值方法。求 √x 等价于解 f(r) = r² - x = 0。牛顿迭代用切线不断逼近根，公式化简后为：

r_{new} = (r + x / r) / 2

直觉：r 和 x/r 一个偏大一个偏小（它们的乘积恒为 x），取平均值会更接近真正的 √x。从 r = x 出发反复迭代，r 快速下降逼近根，当 r² <= x 时停止（此时 r 已是向下取整的整数根）。

牛顿法收敛极快（每次迭代有效位数翻倍，二次收敛），比二分的线性收敛更快，是工程中开方的常用实现。理解「两个互补的估计取平均」这个直觉即可。

五、易错点

mid * mid 溢出：最经典，必须 long 或除法。
返回值：二分返回 hi 而非 lo（lo 停在第一个「平方 > x」的位置，hi = lo - 1 才是答案）。想清楚模板对应关系。
边界 x = 0, 1：sqrt(0)=0, sqrt(1)=1，直接特判返回 x（x < 2 return x），避免牛顿法 x/r 除零。
牛顿法初值：从 r = x 起（对 x≥2 安全），别从 0 起（除零）。

六、把答案写成二分边界不变量

目标谓词 k*k<=x 随 k 从真变假，因此答案是最后一个真位置。循环中 hi 左侧保留可能可行值，lo 右侧保留可能不可行值；结束时 lo=hi+1，hi 就是最大的可行整数。

x=8，初始 lo=1, hi=8
mid=4，16>8 -> hi=3
mid=2，4<=8 -> lo=3
mid=3，9>8 -> hi=2
结束 lo=3, hi=2
hi=2 是最后一个满足 k²<=8 的整数
返回 2

校验维度	本题必须保持的结论
循环/递推不变量	所有小于 lo 且已排除的值可行，所有大于 hi 且已排除的值不可行，答案始终未被错误丢弃。
边界条件	`x=0,1` 直接返回；乘法比较用 long 或 `mid<=x/mid` 防溢出。
复杂度与代价	二分 O(log x)；整数牛顿迭代通常更快收敛，均为 O(1) 显式空间。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

数学题不能只凭样例相信公式，必须同时核对定义域、推导条件和定宽整数边界。本题应先复述这条不变量：所有小于 lo 且已排除的值可行，所有大于 hi 且已排除的值不可行，答案始终未被错误丢弃。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“x=8，初始 lo=1, hi=8”开始手推，最后应得到“返回 2”。
边界复核：x=0,1 直接返回；乘法比较用 long 或 mid<=x/mid 防溢出。
代价复核：二分 O(log x)；整数牛顿迭代通常更快收敛，均为 O(1) 显式空间。
用 0、1、最小合法值和最大合法值检查公式的定义域。
乘法、取绝对值或取负前先判断是否可能触及 Integer.MIN_VALUE 等不对称边界。
若算法依赖单调性、抵消或整除关系，要明确题设保证何时成立、何时必须额外验证。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“所有小于 lo 且已排除的值可行，所有大于 hi 且已排除的值不可行，答案始终未被错误丢弃。”这条正确性主线不能省。

八、常见误区与追问

误区：循环结束应返回 lo。 此模板中 lo 是第一个平方大于 x 的位置，最后一个可行位置是 hi。
误区：mid*mid 使用 int 一定安全。 搜索早期 mid 可能远大于 46340，乘积会溢出并破坏单调判断。
误区：牛顿迭代可以从 r=0 开始。 公式包含 x/r，初值 0 会除零。
追问：为什么牛顿公式取 (r+x/r)/2？ 对 f(r)=r²-x 套用切线迭代并化简即可得到该式。
追问：为什么答案是向下取整？ 题目要求整数部分，等价于寻找最大满足 k²<=x 的 k。
追问：能否把二分上界缩到 x/2？ 对 x>=2 可以用 x/2+1，但 [1,x] 更统一且仍是对数复杂度。

九、加强记忆

整数平方根 sqrt(x)（向下取整）= 找最大的 k 使 k² ≤ x。二分法：在 [1,x] 二分，mid² <= x 则 lo=mid+1、否则 hi=mid-1，返回 hi（平方≤x 的最大整数）；mid*mid 必须用 long 防溢出（或改 mid <= x/mid）。牛顿迭代：r = (r + x/r) / 2 从 r=x 迭代到 r² <= x，收敛极快（两个互补估计取平均）。特判 x<2 返回 x。核心：二分找右边界、乘法防溢出；牛顿取平均、收敛快。

简化版

详细版