本文共 3380 字，大约阅读时间需要 11 分钟。

x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

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

示例 1:

输入: 4输出: 2

示例 2:

输入: 8输出: 2说明: 8 的平方根是 2.82842...,      由于返回类型是整数，小数部分将被舍去。

方法一：二分查找

由于 $x$ 平方根的整数部分 $\text{ans}$ 是满足 $k^2\le x$的最大 $k$ 值，因此我们可以对$k$ 进行二分查找，从而得到答案。

二分查找的下界为 0，上界可以粗略地设定为 $x$。在二分查找的每一步中，我们只需要比较中间元素 $\text{mid}$ 的平方与 $x$ 的大小关系，并通过比较的结果调整上下界的范围。

在判断是否满足条件要用除，不能直接mid * mid，因为如果mid过大会溢出，除的话分2种，一种是x / mid < mid，说明 mid大了， 即最优解在[left,mid],压缩右边界，即right =mid

第2种情况是 x / mid >= mid，说明 mid 太小了，即最优解在[mid+1,right],那么就让下边界往上去一点， left = mid +1，为什么这里不减1呢？因为控制left总比x的根大一点，这样返回最终结果直接返回 left - 1即可，代码如下：

class Solution(object):    def mySqrt(self, x):        """        :type x: int        :rtype: int        """        if x==0 or x==1:            return x        left=0        right = x        while left
   
     x/mid: # 最优解在`[left,mid]`                right =mid             else:             # 最优解在`[mid+1,right]`                left = mid +1        return left-1
   

复杂度分析

时间复杂度：$O(\log x)$ ，即为二分查找需要的次数。

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

方法二：牛顿迭代

，原理是使用函数 $f(x)$ 的泰勒级数的前面几项来寻找方程 $f(x)=0$ 的根。

将函数 $f(x)$ 在 $x_0$ 处展开成泰勒级数:

$$f(x)=f(x_0)+f^{{}^{\prime }}(x_0)(x-x_0)+\frac{1}{2}{f}^{{}^{\prime \prime }}(x_0)(x-x_0{)}^2+\dots \text{\hspace{1em}(5)}$$

取其线性部分，作为 $f(x)$ 的近似，则可用 $f(x_0)+f^{{}^{\prime }}(x_0)(x-x_0)=0$ 的解来近似 $f(x)=0$ 的解，其解为

$$x_1=x_0-\frac{f(x_0)}{f^{{}^{\prime }}(x_0)}\text{\hspace{1em}(6)}$$

由于对 $f(x)$ 的近似只是一阶展开，因此 $r$ 并非 $f(x)=0$ 的解，只能说 $f(x_1)$ 比 $f(x_0)$ 更接近0。于是，考虑迭代求解：

$$x_{n+1}=x_n-\frac{f(x_n)}{f^{{}^{\prime }}(x_n)}\text{\hspace{1em}(7)}$$

由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示：

牛顿法搜索动态示例图：

为了叙述方便，我们用 C 表示待求出平方根的那个整数。显然，C 的平方根就是函数

的零点。我们选择 $x_0=C$ 作为初始值。

由7算式，新的迭代结果

在进行 $k$ 次迭代后，$x_k$ 的值与真实的零点 $sqrtC$ 足够接近，即可作为答案。

class Solution(object):    def mySqrt(self, x):        """        :type x: int        :rtype: int        """        if x==0 or x==1:            return x        C, x0 = float(x), float(x)        while True:            x_n = 0.5*(x0 +C/x0)            if abs(x0 - x_n)<1e-7:                break            x0 = x_n        return int(x0)

细节

为什么选择 $x_0=Cx$ 作为初始值？

因为 $y=x^2-C$ 有两个零点 $-\sqrt{C}$ 和 $\sqrt{C}$ 。如果我们取的初始值较小，可能会迭代到 $-\sqrt{C}$这个零点，而我们希望找到的是 $\sqrt{C}$ 这个零点。因此选择 $x_0=C$ 作为初始值，每次迭代均有 $x_{i+1}<x_i$，零点 $\sqrt{C}$在其左侧，所以我们一定会迭代到这个零点。

迭代到何时才算结束？

每一次迭代后，我们都会距离零点更进一步，所以当相邻两次迭代得到的交点非常接近时，我们就可以断定，此时的结果已经足够我们得到答案了。一般来说，可以判断相邻两次迭代的结果的差值是否小于一个极小的非负数 $ϵϵ$，其中 \epsilonϵ 一般可以取 $10^{-7}$

复杂度分析

时间复杂度：$O(\log x)$ ，此方法是二次收敛的，相较于二分查找更快。

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

参考

力扣（LeetCode） (leetcode-cn.com)]

转载地址：http://pdyzi.baihongyu.com/