九章算法 | Facebook面试题:对x开根 II
程序员文章站
2022-03-08 08:10:01
...
实现 double sqrt(double x)
并且 x >= 0
。
计算并返回x开根后的值。
在线评测地址:LintCode 领扣
例1:
输入: n = 2
输出: 1.41421356
例2:
输入: n = 3
输出: 1.73205081
【题解】
算法:二分
此题有两种做法,一种是牛顿迭代法,一种是二分,这里介绍二分法
- 二分浮点数与寻常二分不同的是
while
中变成了whlie(left+eps<right)
- 注意小数情况,若
x<1
将右边界扩大到1
可避免结果错误(比如0.04=0.2*0.2
)如果我们不将x
右边界扩大到1
,则无法在[0,0.04]
的区间范围内找到正解
复杂度分析
-
时间复杂度
O(log(x))
-
二分的复杂度
-
空间复杂度
O(1)
-
无需额外空间
public class Solution {
/**
* @param x: a double
* @return: the square root of x
*/
public double sqrt(double x) {
double left = 0,right = x,mid;
if (right < 1) {
right = 1;
}
while (left + 1e-12 < right) {
mid = left + (right - left) / 2;
if (mid * mid < x) {
left = mid;
}
else{
right = mid;
}
}
return left;
}
}
更多题解参见:九章算法