Sqrt(x)
出处
Implement sqrt(x), which returns the square root of value x.
Solution
解题分析:首先我们需要明确开根号的性质:
- 负数无效
- 若x为0,则返回0
- 若x属于(0,1),则sqrt(x)属于(x,1)
- 若x为1,则返回1
- 若x大于1,则sqrt(x)属于(1,x)
此外,若x > y,则sqrt(x) > sqrt(y)。情况1,2,4可以作为特例,而对于通常情况(情况3,情况5),我们发现如下两个特性:
- 解落在已知区间
- 存在相对大小关系
进一步地,我们可以将sqrt(x)的所有“候选数”看成是分布在有限区间上的有序数列,对于每个元素,我们通过平方操作比较与待搜索数x的相对大小关系。很明显,这就是二分查找的思想。
Complexity
由于我们利用了二分查找的思想,故复杂度为O(log(x/precision))
Code
double mySqrtHelper(double x, double lowBound, double highBound) {
double precision = 0.00001;
double sqrt = lowBound / 2 + highBound / 2;
if (Math.abs(sqrt * sqrt - x) < precision) {
return sqrt;
} else if (sqrt * sqrt - x > 0) {
return mySqrtHelper(x, lowBound, sqrt);
} else {
return mySqrtHelper(x, sqrt, highBound);
}
}
double mySqrt(double x) {
if (x < 0)
return ERROR;
if (x == 0) {
return 0;
}
if (x == 1) {
return 1;
}
if (x < 1) {
return mySqrtHelper(x, x, 1);
} else {
return mySqrtHelper(x, 1, x);
}
}