LeetCode 69 Sqrt(x)
Implement int sqrt(int x).
Compute and return the square root of x.
求n的平方根与求1n范围内的质数这两个问题都不能用单纯的搜索。如果只是遍历1n/2，则会LTE，因此需要采用别的算法。
1.二分法
常见二分搜索，可以将时间复杂度变为O(logn)，这里需要注意的是返回值为int。
Input: 2 Return: 1
Input: 3 Return: 1
代码如下：
public class Solution {
public int mySqrt(int x) {
if (x <= 0) return 0;
int left = 1, right = x, mid = left + (right - left) / 2;
while (left <= right) {
if (mid == x / mid) return mid;
else {
if (mid > x / mid) right = mid - 1;
else left = mid + 1;
mid = left + (right - left) / 2;
}
}
return right;
}
}
1.牛顿法
将求x=sqrt(n)的问题转为求方程f(x)=0的解：
 = x^2 - n)
牛顿法可以很好快速求得f(x)=0的近似解，迭代公式如下：
}{f^{'}(x_1)} = x_1 - \frac{f(x_1)}{2x_1})
对于本题来说，f(x)的导数即为2x，问题可以进一步转为：
收敛结果为|f(x)|<epsilon或|x1-x2|<epsilon。
代码如下：
public class Solution {
public int mySqrt(int x) {
if (x <= 1) return x;
double x1 = 0, x2 = 1;
while (Math.abs(x1 - x2) > 0.000001) {
x1 = x2;
x2 = x1 / 2 + (double)x / (2 * x1);
}
return (int)x1;
}
}
