二分查找题目：x 的平方根

题目

标题和出处

标题：x 的平方根

出处：69. x 的平方根

难度

3 级

题目描述

要求

给定一个非负整数 $\text{x}$，计算并返回 $\text{x}$ 的算术平方根。

由于返回类型是整数，因此小数部分被舍去，只返回结果的整数部分。

注意：不允许使用任何内置指数函数和算符，例如 $\text{pow(x, 0.5)}$ 或者 $\text{x ** 0.5}$。

示例

示例 1：

输入：$\text{x = 4}$
输出：$\text{2}$

示例 2：

输入：$\text{x = 8}$
输出：$\text{2}$
解释：$\text{8}$ 的算术平方根是 $\text{2.82842...}$，由于小数部分被舍去，因此返回 $\text{2}$。

数据范围

• $\text{0}\le \text{x}\le {\text{2}}^{\text{31}}-\text{1}$

解法一

思路和算法

用 $r$ 表示 $x$ 的算术平方根的整数部分，则 $r$ 是非负整数。

当 $x=0$ 时，$r=0$。当 $x>0$ 时，对于任意非负整数 $y$，当 $y\le r$ 时 $y^2\le x$，当 $y>r$ 时 $y^2>x$。因此可以使用二分查找得到 $r$。

由于 $r$ 一定在范围 $[0,x]$ 内，因此初始时二分查找的范围的下界和上界是 $\text{low}=0$，$\text{high}=x$。

每次查找时，取 $\text{mid}$ 为 $\text{low}$ 和 $\text{high}$ 的平均数向上取整，比较 ${\text{mid}}^2$ 和 $x$ 的大小关系，调整二分查找的范围。

• 如果 ${\text{mid}}^2\le x$，则 $r$ 大于等于 $\text{mid}$，因此在范围 $[\text{mid},\text{high}]$ 中继续查找。

• 如果 ${\text{mid}}^2>x$，则 $r$ 小于 $\text{mid}$，因此在范围 $[\text{low},\text{mid}-1]$ 中继续查找。

当 $\text{low}=\text{high}$ 时，结束查找，此时 $\text{low}$ 即为 $r$，返回 $\text{low}$。

实现方面需要注意处理溢出的情况。

二分查找的过程中，每次取 $\text{mid}=\lceil \frac{\text{low}+\text{high}}{2}\rceil$，等价于 $\text{mid}=\text{low}+\lfloor \frac{\text{high}-\text{low}+1}{2}\rfloor$。由于 $x$ 的取值范围是 $[0,2^{31}-1]$，因此 $\text{high}$ 的最大值可能是 $2^{31}-1$。当 $\text{low}=0$ 且 $\text{high}=2^{31}-1$ 时，$\text{high}-\text{low}+1=2^{31}$，超出了 $32$ 位整型的表示范围，会导致溢出。

为了避免溢出，一种做法是将 $\text{low}$、$\text{high}$、$\text{mid}$ 都声明成 $64$ 位整型，另一种做法是对 $x=0$ 的情况特判。具体做法是，当 $x=0$ 时返回 $0$，当 $x>0$ 时 $x$ 的算术平方根一定大于等于 $1$，因此二分查找的范围的下界和上界初始化为 $\text{low}=1$，$\text{high}=x$，可以避免溢出。

代码

class Solution {public int mySqrt(int x) {if (x == 0) {return 0;}int low = 1, high = x;while (low < high) {int mid = low + (high - low + 1) / 2;if ((long) mid * mid <= x) {low = mid;} else {high = mid - 1;}}return low;}
}

复杂度分析

• 时间复杂度：$O(\log x)$。二分查找的次数是 $O(\log x)$，每次查找的时间是 $O(1)$，时间复杂度是 $O(\log x)$。

• 空间复杂度：$O(1)$。

解法二

预备知识

该解法使用牛顿迭代法计算给定非负整数的算术平方根。牛顿迭代法（Newton’s method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），是牛顿提出的一种在实数域和复数域上近似求解方程的方法。

牛顿迭代法的本质是使用泰勒级数，从初始近似值开始快速向函数的零点逼近。其原理如下。

假设函数 $f(x)$ 的零点是 $r$，则 $r$ 是方程 $f(x)=0$ 的根。选取 $x_0$ 作为 $r$ 的初始近似值，则 $(x_0,f(x_0))$ 是函数 $y=f(x)$ 的图像上的一点，过该点作函数图像的切线，切线方程是 $y-f(x_0)=f^{\prime }(x_0)(x-x_0)$，切线与 $x$ 轴交点的横坐标是 $x_1=x_0-\frac{f(x_0)}{f^{\prime }(x_0)}$，$x_1$ 称为 $r$ 的一次近似值。使用相同的方法，从 $x_1$ 计算得到 $x_2=x_1-\frac{f(x_1)}{f^{\prime }(x_1)}$，$x_2$ 称为 $r$ 的二次近似值。推广到一般情形，当 $k>0$ 时，$x_k=x_{k-1}-\frac{f(x_{k-1})}{f^{\prime }(x_{k-1})}$，$x_k$ 称为 $r$ 的 $k$ 次近似值，上述公式称为牛顿迭代公式。

如果函数的零点存在，则近似值会向零点收敛。当迭代次数达到预设的上限，或者相邻两次近似值足够接近时，即可结束迭代过程。

思路和算法

计算 $x$ 的算术平方根，等价于计算函数 $f(t)=t^2-x(t\ge 0)$ 的零点。该函数的导函数为 $f^{\prime }(t)=2t$，牛顿迭代公式为 $t_k=\frac{1}{2}(t_{k-1}+\frac{x}{t_{k-1}})$。

将 $x$ 作为零点的初始近似值，由于当 $x$ 未到达零点时，$x$ 大于 $\sqrt{x}$，因此每次迭代时都会将 $t_k$ 减小，可以到达 $\sqrt{x}$ 处的零点。

牛顿迭代公式中，自变量 $t$ 出现在分母上。当 $x=0$ 时，$t$ 的初始近似值 $t_0=0$，此时会出现被零除的情况。为了避免出现被零除的情况，应确保 $t>0$，因此当 $x=0$ 时返回 $0$，当 $x>0$ 时使用牛顿迭代法计算 $x$ 的算术平方根。

代码

class Solution {static final double EPSILON = 1e-6;public int mySqrt(int x) {if (x == 0) {return 0;}boolean flag = true;double sqrt = x;while (flag) {double curr = (sqrt + x / sqrt) / 2;if (Math.abs(curr - sqrt) < EPSILON) {flag = false;} else {sqrt = curr;}}return (int) sqrt;}
}

复杂度分析

• 时间复杂度：$O(\log x)$。牛顿迭代法计算算术平方根的时间复杂度是 $O(\log x)$。

• 空间复杂度：$O(1)$。