Stefan Pochmann 的上帝之手（4）开平方

69. x 的平方根

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2

说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
这道题本身很简单，写法也很多，利用现成函数和现成函数组合的这里就不列了。

方法1： 二分查找（9行）

查找k * k <= x的最大k，每次二分查找。

def mySqrt(self, x: int) -> int:
    l, r, ans = 0, x, -1
    while l <= r:
        mid = (l + r) // 2
        if mid * mid <= x:
            ans = mid
            l = mid + 1
        else:
            r = mid - 1
    return ans

方法2：位运算（7行）

查找k * k <= x的最大k，每次确定一位。这里利用了题目信息，输入为整数。

def mySqrt(self, x: int) -> int:
    ans, bit = 0, 1 << 16
    while bit:
        ans |= bit
        if ans * ans > x:
            ans ^= bit
        bit >>= 1
    return int(ans)

方法3： 牛顿法（7~9行）

乐扣官网

寻找C的平方根，就是寻找y = x ** 2 - C的零点。求零点问题，可以使用牛顿法，具体做法为：
从初始点做切线，与x轴的交点作为结果的近似，并进入下一次迭代，直到精度符合要求。

def mySqrt(self, x: int) -> int:
    if x == 0:
        return 0
    
    C, x0 = float(x), float(x)
    while True:
        xi = 0.5 * (x0 + C / x0)
        if abs(x0 - xi) < 1e-7:
            break
        x0 = xi
    
    return int(x0)

另一种写法：

def mySqrt(self, x):
    """
    :type x: int
    :rtype: int
    """
    x0 = x / 2.0, th = 0.5
    while True:
        t = x - x0 * x0
        if abs(t) < th:
            break
        x0 = (x + x0 * x0) / 2 / x0
    return int(x0)

上帝之手（4行）

思路仍旧是牛顿法。

# Python2可以用单斜杠
def mySqrt(self, x: int) -> int:
    r = x
    while r * r > x:
        r = (r + x // r) // 2
    return r

下图证明代码是对的：

出自https://leetcode.com/czhdalao