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
解法
方法一：袖珍计算器算法
「袖珍计算器算法」是一种用指数函数 \(\exp\) 和对数函数 \(\ln\) 代替平方根函数的方法。我们通过有限的可以使用的数学函数，得到我们想要计算的结果。
我们将 \(\sqrt{x}\)写成幂的形式 \(x^{1/2}\)，再使用自然对数 \(e\) 进行换底，即可得到\(\sqrt{x} = x^{1/2} = (e ^ {\ln x})^{1/2} = e^{\frac{1}{2} \ln x}\)这样我们就可以得到 \(\sqrt{x}\)的值了。
注意： 由于计算机无法存储浮点数的精确值，而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程中会存在误差。例如当 \(x = 2147395600\)时，\(e^{\frac{1}{2} \ln x}\)的计算结果与正确值 \(46340\) 相差 \(10^{-11}\)，这样在对结果取整数部分时，会得到 \(46339\)这个错误的结果。
因此在得到结果的整数部分 \(\textit{ans}\)后，我们应当找出 \(\textit{ans}\) 与\(\textit{ans} + 1\)中哪一个是真正的答案。
复杂度分析
时间复杂度：\(O(1)\)，由于内置的 \(exp\) 函数与 \(log\) 函数一般都很快，我们在这里将其复杂度视为 \(O(1)\)。
空间复杂度：\(O(1)\)。
Python3
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
ans = int(math.exp(0.5 * math.log(x)))
return ans + 1 if (ans + 1) ** 2 <= x else ans
C++
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);
}
};
方法二：二分查找
由于 \(x\) 平方根的整数部分 \(\textit{ans}\)是满足 \(k^2 \leq x\)的最大 \(k\) 值，因此我们可以对\(k\)进行二分查找，从而得到答案。
二分查找的下界为 \(0\)，上界可以粗略地设定为 \(x\)。在二分查找的每一步中，我们只需要比较中间元素 \(\textit{mid}\)的平方与 \(x\) 的大小关系，并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算，不会存在误差，因此在得到最终的答案 \(\textit{ans}\)后，也就不需要再去尝试 \(\textit{ans} + 1\)了。
复杂度分析
时间复杂度：\(O(\log x)\)，即为二分查找需要的次数。
空间复杂度：\(O(1)\)。
Python3
class Solution:
def mySqrt(self, x: int) -> int:
l, r, ans = 0, x, -1
while l <= r:
mid = (l + r) // 2
if mid * mid <= x:
ans = mid
l = mid + 1
else:
r = mid - 1
return ans
C++
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;
}
};