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

àì夳堔傛蜴生んèń 2023-10-06 22:53 23阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

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

**提示：**

0 <= x <= 231 \- 1

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

## 2.思路 ##

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

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

（3）袖珍计算器算法  
思路参考[本题官方题解][Link 1]  
**「袖珍计算器算法」是一种用指数函数 exp 和对数函数 ln 代替平方根函数的方法**。我们通过有限的可以使用的数学函数，得到我们想要计算的结果。我们将  x \\sqrt\{x\} x 写成幂的形式 x1/2，再使用自然对数 e 进行换底，即可得到  
![f6d031639f514f41b4e6caff1ddb894c.png][]  
这样我们就可以得到  x \\sqrt\{x\} x 的值了。

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

[Link 1]: https://leetcode.cn/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/
[f6d031639f514f41b4e6caff1ddb894c.png]: https://img-blog.csdnimg.cn/f6d031639f514f41b4e6caff1ddb894c.png