LeetCode_二分搜索_简单_69. x 的平方根

1.题目

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

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

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

提示：

0 <= x <= 2³¹ - 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sqrtx

2.思路

（1）线性搜索
线性搜索是一种比较容易想到的方法，遍历 [0, x] 之间的所有整数，找出 <= x 的最大整数，然后将其返回。不过在编写代码时要注意整数溢出问题。此外需要说明的是，搜索区间虽然是 [0, x]，但是在绝大多数情况下，不会遍历完整个区间，因为当 x 越大时， x 的算术平方根就越小于 x，当找到该值时，直接返回即可。

（2）二分搜索
由于搜索区间 [0, x]是有序的，所以可以使用二分搜索算法来降低查找的时间复杂度。

（3）袖珍计算器算法
思路参考
「袖珍计算器算法」是一种用指数函数 exp 和对数函数 ln 代替平方根函数的方法。我们通过有限的可以使用的数学函数，得到我们想要计算的结果。我们将 $\sqrt{x}$ 写成幂的形式 x^1/2，再使用自然对数 e 进行换底，即可得到

3.代码实现（Java）

//思路1————线性搜索
class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        for (int i = 2; i <= x; i++) {
            int tmp1 = i * i;
            int tmp2 = (i + 1) * (i + 1);
            if (tmp1 == x || (tmp1 < x && tmp2 > x)) {
                return i;
            }
            //出现整数溢出的情况
            if (tmp2 < 0) {
                return i;
            }
        }
        return 1;
    }
}

//思路2————二分搜索
class Solution {
    public int mySqrt(int x) {
        int left = 0, right = x;
        int res = -1;
        while (left <= right) {
            //防止整数溢出
            int mid = left + (right - left) / 2;
            if ((long) mid * mid <= x) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
}

//思路3————袖珍计算器算法
class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        int res = (int) Math.exp(0.5 * Math.log(x));
        return (long) (res + 1) * (res + 1) <= x ? res + 1 : res;
    }
}