二分法
思路:
从0到x不断二分尝试。
代码：
class Solution:
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
牛顿法
思路：
做方程y = x2 - C，C为题目中的非负整数x，则题目变为求方程图像在x正半轴上的交点xi的值。从xi=C开始，做当前点切线与x轴交点为xi+1，当xi和xi+1差值逼近于一个足够小的值时,xi+1为所求答案，否则xi=xi+1，继续迭代。
代码：
class Solution:
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)
原文：https://www.cnblogs.com/nilhxzcode/p/13081526.html