Sqrt(x)
Implement int sqrt(int x).
Compute and return the square root of x.
解法一：牛顿迭代法
求n的平方根，即求f(x)=x-n的零点
设初始值为x，注，不要设为0，以免出现除数为0，见后。
则过(x,f(x))点的切线为g(x)=f(x)+f'(x)*(x-x)
g(x)与x轴的交点为x=x-f(x)/f'(x)
递推关系为x=x-f(x)/f'(x)
当收敛时即为解。
class Solution {
public:
int sqrt(int x) {
double x0 = ;
double x_next = -(x0*x0 - x)/(*x0) + x0;
while(fabs(x0-x_next) > 0.00001)
{
x0 = x_next;
x_next = -(x0*x0 - x)/(*x0) + x0;
}
return x0;
}
};解法二：二分法
注意返回为int，结果会取整。
class Solution {
public:
int sqrt(int x) {
long long low = ;
long long high = x;
long long mid;
while(low <= high)
{
mid = (low+high)/;
long long result = mid*mid;
if(result == x)
return mid;
else if(result > x)
high = mid-;
else
low = mid+;
}
return high;
}
};