描述

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4
输出: 2
示例 2:

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

Python

1.牛顿法
https://www.cnblogs.com/huashanqingzhu/p/6635691.html

class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        sqrt = x
        while sqrt**2 > x:
            sqrt = (sqrt + x/sqrt)/2
            if (sqrt**2-x)<0.05:break # 用来防止超时
        return int(sqrt)

2.二分法
https://blog.csdn.net/ycf74514/article/details/48996383

class Solution:
    def mySqrt(self, x):
        if 0==x:return 0
        l, r = 1, x
        while l <= r:
            mid = l + (r-l)//2 # 防止溢出
            if mid * mid <= x < (mid+1)*(mid+1):
                return mid
            elif x < mid * mid:
                r = mid
            else:
                l = mid

Java

class Solution {
    public int mySqrt(int x) {
        long r = x; // prevent int exceeding
        while (r*r > x)
            r = (r + x/r) / 2;
        return (int) r;
    }
}