69. Sqrt(x)

解题思路

解法1：使用二分查找，从0到x中寻找某个整数数的平方小于x，但是大于这个数的下一个整数，平方大于x，则为结果
解法2：比较巧妙，使用数学公式转换，题目要求不可以使用sqrt或者pow，但是可以使用指数函数

解题遇到的问题

1.解法1：需要注意mid*mid很有可能大于int最大值，所以是long
2.解法2：由于转换成了指数函数，所以求出的ans很有可能需要+1，所以需要特殊处理

后续需要总结学习的知识点

无

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

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