leetcode 072. Finding Square Roots

给定一个非负整数 x ,计算并返回 x 的平方根,即实现 int sqrt(int x) 函数.

正数的平方根有两个,只输出其中的正数平方根.

如果平方根不是整数,输出只保留整数的部分,小数部分将被舍去.

示例 1:

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

输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842…,由于小数部分将被舍去,所以返回 2

提示:

0 <= x <= 2³¹-1

思路：二分

c++

class Solution {
    
public:
    int mySqrt(int x) {
    
        long long left=0,right=x,ans,mid;
        while(left<=right){
    
            mid=left+(right-left)/2; //和 mid=(right+left)/2 等价,但是 left+right 可能会溢出
            if((long long)mid*mid<=x){
      //mid*mid 也可能会溢出,所以用 long long
                ans=mid;
                left=mid+1;
            }
            else
                right=mid-1;
        }
        return ans;
    }
};

python

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

牛顿迭代：

c++:

class Solution {
    
public:
    int mySqrt(int x) {
    
        if(x==0)  //Avoid the following denominator as0的情况
            return 0;
        double x0=x,c=x,xi;
        while(1){
    
            xi=(x0+c/x0)/2;
            if(fabs(x0-xi)<1e-7)
                break;
            x0=xi;
        }
        return x0;
    }
};

python:

class Solution:
    def mySqrt(self, x: int) -> int:
        if x==0:
            return 0
        x0,c=float(x),float(x)
        while 1:
            xi=(x0+c/x0)/2
            if abs(xi-x0)<1e-7:
                break
            x0=xi
        return int(x0)

The formula of Newton's iteration needs to understand its principle,You can refer to this article for a very detailed explanation（写的很详细）：

如何通俗易懂地讲解牛顿迭代法？