[LeetCode] Sqrt(x)

1.Implement int sqrt(int x).
Compute and return the square root of x.
x is guaranteed to be a non-negative integer.

Example 1:
Input: 4
Output: 2

Example 2:
Input: 8
Output: 2

Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.

2.题目要求：求平方根。

3.方法：算一个候选值的平方，然后和x比较大小。采用牛顿迭代法，因为要求x的平方 = n的解，令f(x)=x的平方-n，相当于求解f(x)=0的解，可以求出递推式。

4.代码：
class Solution {
public:
int mySqrt(int x) {
if (x == 0) return 0;
double res = 1, pre = 0;
while (res != pre) {
pre = res;
res = (res + x / res) / 2;
}
return int(res);
}
};