给你一个非负整数 x ，计算并返回 x 的 平方根 。 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

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

输入：x = 8 输出：2 解释：8 的平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 231 - 1

袖珍计算器算法

「袖珍计算器算法」是一种用指数函数 \expexp 和对数函数 \lnln 代替平方根函数的方法。

但是计算机无法存储浮点数的精确值，指数函数和对数函数的参数和返回值均为浮点数，所以在运算过程中会存在误差。在得到结果的整数部分ans 后，我们应当找出 ans+1 和 ans 中哪一个是真正的答案。

demo（C++）

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0)
            return 0;
        int ans = exp(0.5*log(x));
        return ((long long)(ans+1)*(ans+1) <= x ? ans+1 : ans);
    }
};

时间复杂度：O(1)
空间复杂度：O(1)

二分查找

x的平方根K满足 K^2 <= x。可以通过二分查找，左边从0开始，右边从x开始。
要注意的是：

• 两个int相乘的结果是有可能超过int的数字范围的，所以对于mid*mid需要转换为long long 类型。
• 当 mid*mid <= x 时，都需要保留mid的值，作为ans。

原始demo

class Solution {
public:
    int mySqrt(int x) {
        int left = 0, right = x, k = 0;
        while(left <= right) {
            long long mid = left + ((right - left) >> 1);
            if(mid * mid == x) {
                return mid;
            } else if (mid * mid > x) {
                right = mid - 1;
            } else {
                k = mid;
                left = mid + 1;
            }
        }
        return k;
    }
};

优化后：

class Solution {
public:
    int mySqrt(int x) {
        int left = 0, right = x, k = 0;
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if((long long)mid * mid <= x) {
                k = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return k;
    }
};

时间复杂度：O(log n) 二分查找所用时间
空间复杂度：O(1)

牛顿迭代

牛顿迭代法 是一种可以用来快速求解函数零点的方法。
为了求x的平方根，可以构造如下函数

牛顿迭代法的本质是借助泰勒级数，从初始值开始快速向零点逼近。
每次切线和横坐标的交点是

所以，在进行n次迭代之后，xn的值和真实的 值足够接近，就可以得出答案。

一般来说，可以判断相邻两次迭代的结果的差值是否小于一个极小的非负数，一般可以取10^(-6) 或者 10^(-7) 次。
Demo

class Solution {
public:
    int mySqrt(int x) {
        // 牛顿迭代法
        if(x == 0)
            return 0;
        
        double x0 = x;
        while(1) {
            double x1 = 0.5 * (x0 + x / x0);
            if(fabs(x0-x1) < 1e-7) {
                break;
            }
            x0 = x1;
        }

        return x0;
    }
};

时间复杂度与：O(log n) 二次收敛，相较于 二分查找更快。
空间复杂度： O（1）