#69

简单

中频

二分查找

x 的平方根

这是一道围绕算法展开的高频练习。建议先掌握「二分查找」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

算法

原题练习

题目分析

给你一个非负整数 x，要求返回它平方根的整数部分。

也就是说，如果真实平方根不是整数，就只保留向下取整后的结果。

比如 8 的平方根约等于 2.828...，所以答案是 2。

一句话概括：

在整数范围里找到最大的 k，使得 k * k <= x。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：在 [0, x] 上二分答案，找满足 mid * mid <= x 的最大整数 mid。

结构化讲解

面试时怎么讲

开场思路

这题我会用答案二分，查找平方后不超过 x 的最大整数。

核心过程

在 0 到 x 的区间上二分可能答案。
每轮检查 mid * mid 是否小于等于 x。
如果合法，就先记录 mid，再去右侧找更大的合法值。
如果不合法，就把右边界左移，最终得到最大可行整数。

复杂度总结

时间复杂度 O(log x)，空间复杂度 O(1)。

面试补一句：这题的关键词是“最大合法值”，不是“精确命中”。

核心思路

这题不是在数组里找值，而是在整数区间里找边界。真正要找的是“平方后不超过 x 的最大数”，所以本质是答案二分。

步骤讲解

先定义答案搜索区间

平方根一定落在 0 到 x 之间，因此可以在这个闭区间上二分。

为什么这样做：题目要求整数部分，不需要真实求浮点平方根。

对应代码提示：int left = 0, right = x;

判断中点平方是否可行

若 mid * mid <= x，说明当前答案可行，可以尝试更大；否则说明猜大了。

为什么这样做：可行性具备单调性，满足答案二分条件。

对应代码提示：if ((long) mid * mid <= x) { ... }

维护最后一个合法答案

每次中点合法就记录到 ans，然后继续往右找更大的合法值。

为什么这样做：题目要的是向下取整后的平方根，本质就是最大合法值。

对应代码提示：ans = mid; left = mid + 1;

易错点

直接用 int 乘法溢出

当 mid 较大时，mid * mid 可能超过 32 位整数范围。

正确理解：比较时先转成 long，或者改用 mid <= x / mid。

找到合法值就直接返回

这样会漏掉更大的合法整数，答案不一定是向下取整的最大值。

正确理解：合法时继续向右收缩，寻找更大的可行解。

把这题当普通精确匹配二分

多数情况下并不存在平方刚好等于 x 的整数。

正确理解：把目标改写成“最大满足条件的边界值”。

复杂度与适用判断

时间复杂度：O(log x)

空间复杂度：O(1)

比其他方案更好在哪里：比逐个试探更高效，也比牛顿迭代更容易在面试里讲清楚。

适用判断：只要答案有单调可行性，且范围可界定，优先考虑答案二分。

额外提醒

比较平方时要优先防止溢出。

其他语言 / 其他解法

迭代法

使用牛顿迭代法不断逼近平方根的近似解，直到误差小于阈值。

时间复杂度：O(log x)

空间复杂度：O(1)

一句话思路：使用牛顿迭代法不断逼近平方根的近似解，直到误差小于阈值。


class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return (int) x0;
    }
}

数学

使用数学公式 exp(0.5 * log(x)) 计算平方根，然后进行边界检查。

时间复杂度：O(1)

空间复杂度：O(1)

一句话思路：使用数学公式 exp(0.5 * log(x)) 计算平方根，然后进行边界检查。


class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = (int) Math.exp(0.5 * Math.log(x));
        return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }
}

动画演示

如果你还没完全看懂，可以展开动画演示。

二分查找动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

输入值 x:

准备就绪 - 输入一个非负整数，然后点击开始

迭代法动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

输入值 x:

准备就绪 - 输入一个非负整数，然后点击开始

数学动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

输入值 x:

准备就绪 - 输入一个非负整数，然后点击开始

动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。