转发 https://blog.csdn.net/qq_41231926/article/details/82861877
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
思路一：从1开始逐个查找
思路一是最先能想到的简单粗暴的解法。从数字1开始找，一旦找到平方值等于x的数字i，直接返回i。如果找到平方值大于x的数字i，需要返回i - 1。
需要注意的是，为了防止做乘法运算时越界，需要强转为long类型。
时间复杂度是O(sqrt(x))。空间复杂度是O(1)。
JAVA代码：
public class Solution {
public int mySqrt(int x) {
for (long i = 1; i <= x; i++) {
if(i * i > x) {
return (int)(i - 1);
}else if(i * i == x) {
return (int)i;
}
}
return 0;
}
}
思路二：二分查找法
思路一的时间复杂度太高，可以用二分法进行改进。
运算过程中涉及到乘法运算时同样需要强转为long类型防止越界。
时间复杂度是O(logx)。空间复杂度是O(1)。
JAVA代码：
public class Solution {
public int mySqrt(int x) {
int left = 0, right = x / 2 + 1;
while (left <= right) {
long mid = left + (right - left) / 2;
if (mid * mid == x) {
return (int) mid;
} else if (mid * mid < x) {
left = (int) (mid + 1);
} else {
right = (int) (mid - 1);
}
}
return right;
}
}
思路三：牛顿法求解平方根
求一个数n的平方根，相当于求解方程f(x) = x ^ 2 - n的解。
牛顿法的过程如下：
假设某个迭代点的值是Xi，我们求其下一个迭代点的值Xi+1。如上图所示，在（Xi, Yi）点，我们做函数f(x)的切线，其与横轴相交的点就是下一个迭代点Xi+1。
根据直线的方程我们很容易写出关系式：f(Xi) = f(Xi)' * (Xi - Xi+1)。由该式可以推得：Xi+1 = (n + Xi ^ 2) / (2 * Xi)。
那么，循环结束的条件是什么呢？
显然是Xi与Xi+1十分接近时，就可以终止上述迭代过程了。
牛顿法求解的时间复杂度与初值点的选取有关，如果初值点的选取离真实解十分接近，那么迭代速度就更快。如果初值点的选取十分离谱，甚至可能会发散，不收敛。空间复杂度是O(1)。
JAVA代码：
public class Solution {
public int mySqrt(int x) {
double pre = 0, cur = 1;
while (Math.abs(pre - cur) >= 0.000001) {
pre = cur;
cur = (x + cur * cur) / (2 * cur);
}
return (int) pre;
}
}
