LeetCode C++ 69.x的平方根

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

输入：x = 4
输出：2

示例2：

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

0 <= x <= 231 - 1

题目不让用自带的，那么根据根号的算法，就是俩数的乘小于第三个数即可。就有了下面的代码。可是这是有问题的，因为x是int类型的，而且上限很大，最终就导致超限没办法用，读者可以自己拷贝进去试试。最终就把m改成long long型的就解决，缺点就是时间很长。

class Solution {
public:
    int mySqrt(int x) {
        long long m = 1;
        while(m * m <= x){
            m++;
        }
        return m-1;
    }
};

用指数函数 expexp 和对数函数 lnln 代替平方根函数的方法。
exp是e得n次方。这个法我是没看懂，但是很基础。

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);
    }
};

二分查找的下界为 00，上界可以粗略地设定为 xx。在二分查找的每一步中，我们只需要比较中间元素 textit{mid}mid 的平方与 xx 的大小关系，并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算，不会存在误差，因此在得到最终的答案 textit{ans}ans 后，也就不需要再去尝试 ans+1了。

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

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (fabs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return int(x0);
    }
};