题目

实现 int sqrt(int x) 函数。

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

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

示例1：
```
输入: 4
输出: 2
```

示例2：

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

解答

解法1：

思路：
- 首先用特判，处理掉 x=1 的特殊情况；
- 接着用二分法，找到x平方根的整数部分；
- 二分法的结束条件：跳出循环之前的最后一次循环，left == right, 此时得到 mid == left，因此：
  - 如果 mid > x * mid ，则 x 的平方根必然为比left略小一点的某个值，所以最后结果返回 left - 1；
  - 如果 mid <= x * mid , 则 x 的平方根必然为比left略大一点某个值，又因为执行了 left = mid +１, 所以最后结果返回 left - 1；

代码：

    def mySqrt(self, x):
        """
        (Knowledge)

        函数功能描述: 传入一个数字，返回其平方根的整数部分

        思路：
        1. 首先用特判，处理掉x=1的特殊情况；
        2. 接着用二分法，找到x平方根的整数部分；

        二分法的结束条件：跳出循环之前的最后一次循环，left == right, 此时得到 mid == left，因此：
            
            - 如果mid > x * mid，则 x 的平方根必然为比left略小一点的某个值，所以最后结果返回 left - 1
            
            - 如果mid <= x * mid, 则 x 的平方根必然为比left略大一点某个值，又因为执行了 left = mid +１, 所以最后结果返回 left - 1
            
        """
        if x < 2:
            return x
        left, right = 1, x // 2
        while left <= right:
            mid = left + (right - left) // 2
            if mid > x / mid:
                right = mid - 1
            else:
                left = mid + 1
        return left - 1

解法2：

思路：
- 使用 牛顿迭代法 近似求平方根；=> 牛顿迭代法求平方根证明
- 最终得到的迭代公式：
  - next => 等式左边为下一个近似值，等式右的next表示上一个近似值;
  - input => 输入值。

代码：

    def mySqrt2(self, x):
        """
        (Knowledge)

        算法说明：使用牛顿迭代法，近似求平方根
        牛顿迭代法求平方跟的证明详见 => https://www.cnblogs.com/upcan/p/9907402.html

        最终得到迭代公式： next = 1/2 * (next + input / next)
            - next => 等式左边为下一个近似值，等式右的next表示上一个近似值
            - input => 输入值
        """

        # 首先猜测一个初始的预测值
        next = x / 2

        # 运行20次迭代（这个迭代次数取决于需要的精度，迭代次数越多，得到的结果越精确）
        for k in range(20):
            next = 1 / 2 * (next + x / next)

        # 根据题意，进行向下取整
        return math.floor(next)

测试验证

import math

class Solution:
    def mySqrt(self, x):
        """
        (Knowledge)

        函数功能描述: 传入一个数字，返回其平方根的整数部分

        思路：
        1. 首先用特判，处理掉x=1的特殊情况；
        2. 接着用二分法，找到x平方根的整数部分；

        二分法的结束条件：跳出循环之前的最后一次循环，left == right, 此时得到 mid == left，因此：
            
            - 如果mid > x * mid，则 x 的平方根必然为比left略小一点的某个值，所以最后结果返回 left - 1
            
            - 如果mid <= x * mid, 则 x 的平方根必然为比left略大一点某个值，又因为执行了 left = mid +１, 所以最后结果返回 left - 1
            
        """
        if x < 2:
            return x
        left, right = 1, x // 2
        while left <= right:
            mid = left + (right - left) // 2
            if mid > x / mid:
                right = mid - 1
            else:
                left = mid + 1
        return left - 1

    def mySqrt2(self, x):
        """
        (Knowledge)

        算法说明：使用牛顿迭代法，近似求平方根
        牛顿迭代法求平方跟的证明详见 => https://www.cnblogs.com/upcan/p/9907402.html

        最终得到迭代公式： next = 1/2 * (next + input / next)
            - next => 等式左边为下一个近似值，等式右的next表示上一个近似值
            - input => 输入值
        """

        # 首先猜测一个初始的预测值
        next = x / 2

        # 运行20次迭代（这个迭代次数取决于需要的精度，迭代次数越多，得到的结果越精确）
        for k in range(20):
            next = 1 / 2 * (next + x / next)

        # 根据题意，进行向下取整
        return math.floor(next)



if __name__ == '__main__':
    solution = Solution()
    print(solution.mySqrt(9))
    print(solution.mySqrt(8))
    print(solution.mySqrt(10))
    print(solution.mySqrt(7))
    print(solution.mySqrt2(9))
    print(solution.mySqrt2(8))
    print(solution.mySqrt2(10))
    print(solution.mySqrt2(7))