求平方根

问题简述

实现函数 int sqrt(int x).
计算并返回 x 的平方根（向下取整）

求平方根_牛客题霸_牛客网

思路1：二分查找

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 
# @param x int整型 
# @return int整型
#
class Solution:
    def sqrt(self , x: int) -> int:
        # write code here
        assert x >= 0
        if x == 0: return 0
        
        l, r = 1, x
        while l < r:
            mid = (l + r) // 2
            if mid <= x / mid:
                if mid + 1 > x / (mid + 1):
                    return mid
                l = mid + 1
            else:
                r = mid - 1
        
        return 1

思路2：牛顿迭代法

• 牛顿迭代法求根公式：$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$；

• 本题中（为避免歧义，将问题修改为求 $a$ 的根），则 $f(x) = x^2 - a$，带入上式，得 $x_{n+1} = x_n - \frac{x_n^2-a}{2x_n}=(x_n+a/x_n)/2$，初始化 $x_0=a$，迭代计算 $x_n$，直到 $|x_{n+1}-x_n|$ 满足误差要求；

Python

class Solution:
    def sqrt(self, a: int) -> int:
        # write code here
        assert x >= 0
        if a == 0: return 0

        eps = 1e-1  # 精度要求

        r = a
        while True:
            t = (r + a / r) / 2
            if abs(r - t) < eps:
                break
            r = t

        return int(r)