【题目描述】
Implement intsqrt(int x).
Compute and return the square root ofx.
实现int sqrt(int x)函数，计算并返回x的平方根。
【题目链接】
www.lintcode.com/en/problem/sqrtx/
【题目解析】
问题可以转化为从1 ~ x寻找目标数字，于是二分法就可以提供O(log(n))的时间复杂度，O(1)的空间复杂度。
此外，可以考虑使用牛顿法:x_(n+1) = x_n - f(x_(n))/f'(x_(n))
其中S 满足 x = sqrt(S),f(x_(n)) = (x_(n)) ^ 2 - S
于是x_(n+1) = x_(n) - ((x_(n))^ - S) / (2 * x_(n)) = 1/2 * (x_(n) + S / x_(n))
这样只需迭代x_(n+1) = 1/2 * (x_(n) + S/x_(n)),
直到| x_(n+1) - x_(n) | < 1
【参考答案】
