LeetCode 补充题 149. 实数平方根的近似计算
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 69. x 的平方根
:::
给定非负实数
x与允许的绝对误差epsilon，不调用平方根库函数，返回一个与真实平方根之差不超过epsilon的近似值。需要六位小数时，可取更小的内部误差后将结果格式化为六位小数。
示例 1：
输入：
x = 2, epsilon = 0.000001
输出：约 1.414214
解释： 1.414214 与真实平方根的差小于10⁻⁶；允许输出其他满足误差的值。
示例 2：
输入：
x = 0.25, epsilon = 0.000001
输出：约 0.5
解释：x小于 1 时，平方根可以大于x，不能把右边界固定为x。
提示：
- 本实现使用
double：0≤x≤10¹²，10⁻⁹≤epsilon≤10⁻³。 - 输出是近似实数，不是向下取整的整数。
题意分析
在非负区间上，平方随数值单调增加，因此可通过中点平方与
x的比较排除一半候选。目标是根本身的绝对误差，应控制候选区间宽度，而不是仅判断平方后的差值。
解法：按区间宽度停止的实数二分
核心思路
[!blue]
初始化
[left,right] = [0,max(1,x)]：当x >= 1时平方根不超过x，当x < 1时平方根可能大于x，但不超过 1，因此该区间始终包含真根。若
mid * mid > x，真根位于中点左侧，令right = mid；否则令left = mid。每次都保留真根所在半区，不使用整数二分中的mid ± 1。区间宽度不超过
epsilon后返回中点，精确运算下误差至多为宽度的一半。题目给定的数值和误差范围也为浮点舍入留出了余量；格式化为固定小数位时会另有舍入误差，不能将显示精度与计算阈值混为一谈。
解题步骤
- 初始区间取 [0,max(1,x)]，同时覆盖 x 小于 1 的情况。
- 比较中点平方与 x，保留包含平方根的半区。
- 区间宽度不超过 epsilon 时返回中点。
代码实现
class Solution {
public double realSqrt(double x, double epsilon) {
double left = 0;
double right = Math.max(1, x);
while (right - left > epsilon) {
double mid = left + (right - left) / 2;
if (mid * mid > x) {
right = mid;
} else {
left = mid;
}
}
return left + (right - left) / 2;
}
}
func realSqrt(x, epsilon float64) float64 {
left, right := 0.0, max(1.0, x)
for right-left > epsilon {
mid := left + (right-left)/2
if mid*mid > x {
right = mid
} else {
left = mid
}
}
return left + (right-left)/2
}
复杂度分析
- 时间复杂度：$O(\log (\max (1,x)/epsilon))$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
根始终在区间中，所以中点误差不超过区间宽度的一半；整数开方的下取整规则不适用于这里。
易错点总结
[!yellow]
epsilon 必须大于 0；不能把浮点近似误差与整数开方的截断规则混淆。六位小数格式化会引入至多约半个末位单位的舍入误差。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 69. x 的平方根 | 简单 | 同样二分平方根，原题求整数下界，本题以区间宽度控制浮点误差。 |
| 367. 有效的完全平方数 | 简单 | 同样比较平方与目标，原题要求精确整数相等，本题返回允许误差的近似值。 |