题目

难度：★★☆☆☆
类型：数组

实现 int sqrt(int x) 函数。

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

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

示例

示例 1:

输入: 4
输出: 2
示例 2:

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

解答

方案1：二分法

这道题目由于只要求取开平方后的整数部分，因此搜索范围有限，可以考虑使用二分法。

构造数组从0到输入x，该数组中每个元素与其所在位置相等，定义两个指针，左指针left和右指针right，初始位置分别位于数组两端；
执行循环，循环的控制条件是左指针不能跑到右指针的右边去，每轮循环获得中点所在位置，查看该数的平方s与输入x之间的大小关系：
（1）s == x：相当于找到了开方结果，直接返回这个数；
（2）s > x：平方结果较大，删除数组右半部分
（3）s < x：平方结果较小，删除数组左半部分
跳出循环时，返回右指针所在位置。

为何是右指针？如果一个数字x开平方x_quare不是整数，那么要跳出循环的前一个状态一定是left=right或者left+1=right，不过无论如何left的位置都是n的向上取整，那么最后一个循环内部所执行的操作就必定是右指针左移到左指针左边，也就是n的向下取整。

class Solution:
    def mySqrt(self, x):
        # 首先，我们构造一个数组，数组中的每个值即为其所在位置（下标），数组范围是从0到x
        left, right = 0, x                          # 初始化左指针和右指针为数组两端数字

        while left <= right:                        # 要求左指针不大于又指针，当满足条件时执行
            # 求取中点位置（位置即为该位置的数），如果数组长度为偶数，取中间偏左的一个
            mid = left + (right - left) // 2

            if mid ** 2 > x:                        # 如果中点的平方大于输入x
                right = mid - 1                     # 抛弃数组右半部分
            elif mid ** 2 < x:                      # 如果中点的平方小于输入x
                left = mid + 1                      # 抛弃数组左半部分
            else:                                   # 如果中点的平方即为输入x
                return mid                          # 直接返回中点即可

        return right                                # 返回结果

方案2：牛顿法

假设我们要求b的平方根 $\sqrt{b}=x_{0}$ ，相当于求 $x^{2}=b$ 的解，或者说，是函数 $f\left ( x \right )=x^{2}-b$ 与x轴的交点坐标，我们使用牛顿法计算估算这个坐标。

如图所示是牛顿法的流程示意图，假设我们要计算b=10的平方根，构造函数 $f\left ( x \right )=x^{2}-10$ ，求该函数与x轴交点的横坐标，我们首先寻找在曲线上的一个点，点的横坐标为10，做这个点的切线，该切线与x轴有一个交点，然后过该点做垂线，与曲线又有一个交点，再次沿着该点做切线，重复上述流程，很显然，随着迭代的进行，垂线与曲线的交点（即下一轮的切点）会不断逼近曲线与x轴的交点，当垂线与曲线的交点的纵坐标小于一定阈值时，我们将这个切点的横坐标近似认为是曲线与x轴交点的横坐标。

牛顿法求取平方根

我们的工作就是每次寻找下一轮切点的坐标。假设当前切点的坐标为 $\left ( x_{c}, y_{c} \right )$ ，根据抛物线导数公式可得，该切点出切线的斜率为 $2 x_{c}$ ，设切线与x轴交点为 $\left ( x_{n}, 0 \right )$ ，那么根据直线的斜率定义，可以得到：
$\frac{y_{c}-0}{x_{c}-x_{n}}=2x_{c}$
解得：
$x_{n}=x_{c}-\frac{y_{c}}{2x_{c}}$
那么过该交点作垂线后与曲线的交点纵坐标为：
$y_{n}=f\left ( x_{n} \right )=x_{n}^{2}-b$
下一个切点的坐标即为 $\left(x_{n}, y_{n} \right)$

不断比较当前切点纵坐标与零之间的差值，当小于某一阈值时，结束循环。

class Solution:
    def mySqrt(self, x):

        b = x                               # 改写一下，显得更清楚
        x_c, y_c = b, b * b - b             # 初始化切点坐标
        while abs(y_c) > 1e-4:              # 满足阈值条件
            x_n = x_c - y_c / (2 * x_c)     # 计算下一个切点横坐标，推导公式见上文
            y_n = x_n * x_n - b             # 计算下一个切点纵坐标，推导公式见上文
            x_c, y_c = x_n, y_n             # 更新当前坐标

        return int(x_c)                     # 取出结果的整数部分即可

如有疑问或建议，欢迎评论区留言~