69. x 的平方根（Sqrt(x)）

频次 ★★★ · 难度 🟢 · 高频：全厂

题目

非负整数 x，返回其整数平方根（截断小数），不允许用内置 sqrt 函数。

示例：

输入: 8
输出: 2    （sqrt(8) ≈ 2.828, 返回 2）

思路

二分查找整数平方根：在 [0, x] 中找最大的 k 使 k² ≤ x——即求”最后一个满足条件的位置”（右边界二分）。

• mid² ≤ x 时 l = mid（mid 可能是答案，向右扩张）
• 否则 r = mid - 1
• mid 取右中位数 (l + r + 1) / 2 防死循环

注意 mid * mid 可能溢出 int，用 long 或 mid <= x / mid 规避。

代码

public int mySqrt(int x) {
    if (x <= 1) return x;                // 0 和 1 特判
    int l = 1, r = x / 2;                // 平方根不会超过 x/2（x>1 时）
    while (l < r) {
        int mid = l + (r - l + 1) / 2;   // 右中位数
        if (mid <= x / mid)              // 等价于 mid*mid <= x，防止溢出
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

复杂度

• 时间：O(log x)
• 空间：O(1)

边界条件

• x = 0：返回 0
• x = 1：返回 1
• x = Integer.MAX_VALUE：mid <= x / mid 避免溢出；若用 mid * mid 会溢出变负数导致判断错误
• 完全平方数（如 16）：mid 恰好命中，返回 4

变式

• 367. 有效的完全平方数：二分判等（mid² == x），不需返回位置
• 精度版（浮点平方根）：二分或牛顿迭代，循环条件改 r - l > 1e-6
• 牛顿迭代法：x_{n+1} = (x_n + x / x_n) / 2，收敛比二分快，但本题要求整数，二分够用

易错点

• mid * mid 溢出：int 范围约 21 亿，mid > 46340 时 mid² 超出 int 上限。解法：用 mid <= x / mid 除法判等，或 long 转型
• 右中位数防死循环：l + (r - l + 1) / 2，当 l + 1 = r 时 mid = r，防止 l = mid 后原地循环
• 上界设为 x / 2：除 0 和 1 外，√x ≤ x/2；设为 x 也能过就是多几步

面试追问

• 怎么处理大数溢出？ 展示 mid <= x / mid 的写法，说明比 (long)mid * mid 更省空间（面试官的预期答案通常是除法，不是转型）
• 能否用牛顿迭代？ 能，但整数场景下二分更直观且无浮点精度问题。先答”能用”，再补一句”但面试题的预期解法是二分”让面试官知道你有所取舍
• 保留小数的版本呢？ 浮点二分改精度条件，或牛顿迭代，返回 double

关联题

• 同套路：367. 有效的完全平方数 —— 判等而非找边界
• 进阶：33. 搜索旋转排序数组 —— 二分在非单调场景的拓展
• 知识点：二分查找右边界模板见二分查找；整数溢出防护见Java基础