69. x 的平方根（二分、牛顿法）

解答

1.我的方法

class Solution:
    def mySqrt(self, x: int) -> int:
        divisor = 1
        if x == 0:
            return 0
        while divisor <= x:
            solu = x // divisor
            if abs(solu - divisor) <= 1:
                return min(solu, divisor)
            divisor += 1

不过超出时间限制了。。。这应该是O（n）叭，不知道为啥超出了。

改进一下，将while的条件设为divisior <= x/2。因为一般而言x的平方根不大于它的一半。但是存在个例。x=1,2,3时x的平方根会大于它的一半，就单独讨论。改进后如下：

def mySqrt(x):
    divisor = 1
    if x == 0:
        return 0
    if x == 2 or x == 3 or x == 1:
        return 1
    while divisor <= x/2:
        solu = x // divisor
        if abs(solu - divisor) <= 1:
            return min(solu, divisor)
        divisor += 1

依旧超出时间范围，fine

2.二分法

   def mySqrt(self, x: int) -> int:
        left = 0
        right = x//2
        if x == 0:
            return 0
        while left <= right:
            # 一定要取右中点，不能取左中点，不然可能进入死循环（4和1的中点是2或3）
            mid = (left + right + 1) >> 1  # 取右中点
            # mid = left + (right - left + 1) // 2  # 取左中点
            square = mid * mid

            if square <= x:
                left = mid
            else:
                right = mid - 1
        return left

well，超出时间范围.....
3.牛顿法
设f(x) = x^2 - a. 这里a就是输入的值，x就是输出的平方根值。
https://blog.csdn.net/batuwuhanpei/article/details/51979831
https://leetcode-cn.com/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/
讲解了牛顿法原理

    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        cur = 1  # 随意定一个正的初值
        pre = 0
        while abs(cur - pre) >= 1e-6:
            pre = cur
            cur = pre - (pre * pre - x) / (2 * pre)
        return int(cur)