LeetCode 69. x 的平方根

约 5 分钟
文章信息 26 个分类 2 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 100-200 面试经典 150 题 腾讯 字节 阿里 微软 美团 拼多多 京东 小米 百度 网易 小红书 快手 滴滴 携程 虾皮 商汤 TP-LINK 猿辅导 作业帮
标签
数学 二分查找

题目描述

✅ 69. x 的平方根

image-20260928190746239

题意分析

给定非负整数 x，返回它的算术平方根向下取整后的整数。也就是找到 r，使得 r² <= x < (r + 1)²；这里是舍去小数部分，不是四舍五入。

x 不一定是完全平方数，不能只查找平方恰好等于 x 的数。x 为 0 或 1 时答案就是自身；题目不允许直接使用开方函数或幂运算求结果。

解法：二分查找最大可行值

核心思路

[!blue]

非负整数越大，平方也越大。因此，满足 k² <= x 的候选形成一个连续区间，答案就是这个区间的最右端：mid 可行时，更小的数都可行；mid 不可行时，更大的数也都不可行。每次都能排除一半候选，适合二分查找。

先处理 x < 2，其余情况在 [1, x / 2] 中搜索。这个上界足够：若答案至少为 2，就有 k² >= 2k，再由 k² <= x 得到 k <= x / 2；答案为 1 时也在区间内。

left、right 表示还需检查的闭区间，ans 保存已经确认的最大可行值。若 mid² <= x，先记下 mid，再令 left = mid + 1，寻找更大的可行值；否则令 right = mid - 1，排除 mid 以及更大的数。区间为空时，没有更大的可行候选，ans 就是答案。

比较平方时还要避免溢出。Java 先把 mid 转成 long 再相乘；Go 判断 mid <= x / mid，对正整数 mid，它与 mid² <= x 等价。搜索下界为 1，因此除法不会遇到零。

解题步骤

  1. x < 2 时直接返回 x，处理平方根为零或一的边界。
  2. 初始化 left = 1、right = x / 2、ans = 1，使用闭区间二分。
  3. 只要 left <= right，取中点 mid，安全判断其平方是否不超过 x。
  4. 可行时更新 ans = mid，并从 mid + 1 继续向右找；不可行时把右边界缩到 mid - 1。
  5. 搜索区间为空后返回 ans。

代码实现

class Solution {
    public int mySqrt(int x) {
        if (x < 2) {
            return x;
        }

        int left = 1;
        int right = x / 2;
        int ans = 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // 先提升类型再平方，避免比较之前已经溢出。
            if ((long) mid * mid <= x) {
                ans = mid;
                // 当前值可行仍需向右找，目标是最大的可行整数。
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return ans;
    }
}

func mySqrt(x int) int {
    if x < 2 {
        return x
    }

    left, right, ans := 1, x/2, 1
    for left <= right {
        mid := left + (right-left)/2
        // 中点始终为正，用除法比较避免平方溢出。
        if mid <= x/mid {
            ans = mid
            // 当前值可行仍需向右找，目标是最大的可行整数。
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(\log x)$，x >= 2 时每轮将搜索区间缩小约一半；x < 2 时为 $O(1)$。
  • 空间复杂度：$O(1)$，只保存边界、中点和当前答案。

关键点总结

[!green]

  • 目标是满足平方不超过 x 的最大整数，利用的是可行性的单调变化。
  • ans 保留已经找到的可行值，向右继续搜索负责确认它是否最大。
  • 搜索边界和乘法类型都要覆盖题目的整数范围。

易错点总结

[!yellow]

  • 只在 mid² == x 时返回，会漏掉不是完全平方数的输入；应寻找最后一个 mid² <= x 的值。
  • 找到任意可行值就返回，尚未确认右侧是否还有更大的答案。
  • Java 写成 (long) (mid * mid) 仍会先在 int 中溢出，必须在乘法前转换类型。
  • 使用除法判断时若允许 mid = 0，会发生除零；这里先处理小输入，再从 1 开始查找。
  • 退出时 left 已经越过最大可行值，直接返回它会多一；代码返回保存下来的 ans。

相似题目

题目 难度 关联与区别
367. 有效的完全平方数 简单 同样比较平方与目标，原题判断是否恰为完全平方，本题返回平方根的整数下界。
441. 排列硬币 简单 同样对单调增长的数值表达式二分，原题找满足三角数不超过n的最大层数。
34. 在排序数组中查找元素的第一个和最后一个位置 中等 在有序或具有单调判定的区间进行边界二分；本题以平方是否超过输入作为判定，该题定位等于目标值的左右边界。
35. 搜索插入位置 简单 在有序或具有单调判定的区间进行边界二分；本题以平方是否超过输入作为判定，该题寻找第一个不小于目标的位置。
补充题 149. 实数平方根的近似计算 中等 都在单调区间内二分平方根；补充题以误差阈值代替整数边界。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/58773597
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！