0069. Sqrt(x)

题目信息

题号:
  1. x 的平方根

难度:

Easy

主题:

数学、二分查找、牛顿迭代、整数边界

原题:

LeetCode 0069

重点:

从逐个试探平方根,推导到单调边界二分与整数牛顿迭代

题目重述

给定非负整数 x,返回 sqrt(x) 向下取整后的整数。不能使用内置指数函数或运算符, 例如 pow(x, 0.5)。

约束为 0 <= x <= 2^31 - 1。返回值 r 必须满足:

r^2 <= x < (r + 1)^2

自建示例

输入:x = 50
输出:7

7^2 = 49 <= 50,而 8^2 = 64 > 50,所以向下取整后得到 7。

输入:x = 2147395600
输出:46340

该输入恰好等于 46340^2,因此返回 46340。

输入:x = 8
输出:2

sqrt(8) 位于 2 与 3 之间,向下取整后得到 2。

C++ 实现

class Solution {
private:
    int linearSearch(int x) {
        if (x < 2) {
            return x;
        }

        int answer = 1;
        for (int candidate = 2;
             candidate <= x / candidate;
             ++candidate) {
            answer = candidate;
        }
        return answer;
    }

    int binaryLastTrue(int x) {
        if (x < 2) {
            return x;
        }

        int left = 1;
        int right = x / 2 + 1;
        int answer = 1;

        while (left <= right) {
            const int middle = left + (right - left) / 2;
            if (middle <= x / middle) {
                answer = middle;
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return answer;
    }

    int newtonIteration(int x) {
        if (x < 2) {
            return x;
        }

        long long estimate = x;
        while (estimate > x / estimate) {
            estimate = (estimate + x / estimate) / 2;
        }
        return static_cast<int>(estimate);
    }

public:
    int mySqrt(int x) {
        return binaryLastTrue(x);
    }
};

题解

逐个验证候选值

向下取整平方根不是寻找一个一定满足 candidate^2 == x 的整数,而是寻找满足 candidate^2 <= x 的最大整数。

linearSearch 从 1 开始递增候选值。只要当前候选仍合法,就把它记录为答案;第一个不合法值之后的 所有整数平方只会更大,因此无需继续检查。

候选最多增长到 sqrt(x) 附近,时间复杂度为 O(sqrt(x))。这一步直接对应定义,也揭示了可用于优化的 单调结构。

除法形式的平方判断

若直接计算 candidate * candidate,乘积可能超过 32 位有符号整数范围。对于正整数 candidate,下面两种 判断等价:

candidate^2 <= x
candidate <= x / candidate

整数除法向下取整。若 candidate^2 <= x,则商至少为 candidate;若平方大于 x,则商必小于 candidate。代码因此不需要执行可能溢出的乘法。

最后真值边界

定义谓词:

valid(candidate) = candidate <= x / candidate

候选值从小到大时,valid 只会从 true 变为 false。目标就是最后一个使谓词为真的整数,可以使用 二分查找。

当 middle 合法时,它已经是一个可行答案,同时右侧仍可能存在更大的合法值,因此记录 middle,并令 left = middle + 1。当 middle 非法时,它及其右侧全部非法,因此令 right = middle - 1。

answer 始终保存已经验证过的最大合法候选。循环结束时搜索区间为空,所有更大的候选都已排除, answer 就是向下取整平方根。

搜索区间

x 为 0 或 1 时,平方根就是自身,代码直接返回。

对于 x >= 2,平方根不会超过 x / 2 + 1,因此二分区间可以初始化为:

[1, x / 2 + 1]

即使使用更宽的 [1, x],结果仍正确;较紧的右边界只减少常数级搜索范围。

边界演化

以 x = 27 为例:

区间

中点

判断

更新

[1, 14]

7

7 > 27 / 7

right = 6

[1, 6]

3

3 <= 27 / 3

记录 3,left = 4

[4, 6]

5

5 <= 27 / 5

记录 5,left = 6

[6, 6]

6

6 > 27 / 6

right = 5

搜索结束后,最后一个合法候选为 5。

整数牛顿迭代

方程 r^2 = x 的牛顿更新式为:

next = (estimate + x / estimate) / 2

newtonIteration 从 estimate = x 开始。只要 estimate > x / estimate,当前估计的平方就大于 x, 仍需继续缩小。

在该条件下,x / estimate < estimate,所以新的整数估计严格小于旧值。实数算术中的两项平均值不会低于 sqrt(x);向下取整后也不会越过目标整数的下界。估计值因此从上方单调下降,最终停在 floor(sqrt(x))。

停止时满足 estimate <= x / estimate,即 estimate^2 <= x。若它还能再增加 1,牛顿序列就不会从上方 越过该更大合法整数,因此当前值正是最大合法整数。

方法关系

线性试探按顺序检查所有候选值,直接建立“最后一个合法整数”的目标。二分查找利用合法性随候选值单调变化, 跳过大部分候选。牛顿迭代不再维护显式搜索区间,而是利用方程结构快速缩小过大的估计。

公开入口选择 binaryLastTrue。它的边界不变量明确,只使用整数除法,并能稳定处理 2^31 - 1 附近的输入。

复杂度分析

设输入为 x:

  • 线性试探时间 O(sqrt(x)),额外空间 O(1);

  • 二分查找时间 O(log x),额外空间 O(1);

  • 牛顿迭代使用常数空间,迭代轮数不超过 O(log x),实际通常更少。

边界处理

  • x = 0 或 x = 1 时直接返回自身;

  • 完全平方数会被识别为最后一个合法候选;

  • 非完全平方数返回小于真实平方根的最大整数;

  • 平方比较使用 candidate <= x / candidate,避免 32 位乘法溢出;

  • 牛顿法只在 x >= 2 时执行,因此除数 estimate 始终为正。