给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

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

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

 

示例 1：

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

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

---

二分查找的方法

在0和x中查找

func mySqrt(x int) int {
    l, r := 0, x
    ans := -1
    for l <= r{
        mid := l + (r-l)/2
        if mid*mid <= x{
            ans = mid
            l = mid + 1
        }else{
            r = mid - 1
        }
    }
    return ans
}

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

    }
};

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

TODO:求非整数，比如精确到0.01

袖珍计算器算法

「袖珍计算器算法」是一种用指数函数 exp 和对数函数 ln 代替平方根函数的方法。我们通过有限的可以使用的数学函数，得到我们想要计算的结果。

x = e^lnx x^1/2 = e^(1/2 * lnx)

class Solution {
public:
    int mySqrt(int x) {
        // x = e^0.5*lnx
        if (x == 0) return 0;
        int ans = exp(0.5 * log(x));
        // 浮点数计算存在误差，可能会算小了
        return (long)(ans+1)*(ans+1) <= x ? ans + 1 : ans;
    }
};

牛顿迭代法

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;
        // 注意要申明为double，float精度不够,case:2147395599
        double x0 = x, C = x;
        while (true) {
            // 构造函数y = x^2 - C; 取(x0, x0*x0 - C)这一点的切线，求其与x轴交点得到(0.5*(x0+c/x0)))
            double x1 = 0.5 * (x0 + C / x0);
            if (x0 - x1 < 1e-7) {
                return int(x1);
            }
            x0 = x1;
        }
    }
};