69. Sqrt(x)
Implement int sqrt(int x).
Compute and return the square root of x.
要求设计一个计算算数平方根的函数，那么我们只需要在0~x的范围内查找，寻找到符合root*root==x的元素，返回即可。
思路比较简单，具体实现有两种方式:
- 二分查找法
- 牛顿迭代法
第一种方法比较容易想到，但考虑到这个题要求返回值为int类型，所以我们的循环条件不能是简单的root*root==x,而需要仔细加以考虑，对下面一个序列进行分析:
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5
综上我们可以知道当if(x>=root*root&&x<(root+1)*(root+1))时，便应该return (int)root;,具体请见代码，如下:
/*solution1 use binary-search 8ms*/
class Solution {
public:
int mySqrt(int x) {
if(x<0)
return -1;
int low=0,high=x;
double root=0;
while(low<=high){
root=low+(high-low)/2;
if(x>=root*root&&x<(root+1)*(root+1))
return (int)root;
if(root*root<x)
low=root+1;
else
high=root-1;
}
return -1;
}
};
2.牛顿迭代法
首先看方法的说明:
数学推导很简单，最终得到的递推公式是:
我们用一个last变量记录上一次迭代的结果，res记录每次迭代的新结果，当last和res相等时，则说明精度已经达到我们的要求，返回即可，代码如下:
*solution 2 use Newton's method*/
class Solution {
public:
int mySqrt(int x) {
if(x<0)
return -1;
if(x==0)
return 0;
double last=0,res=1;
while(res!=last){
last=res;
res=(res+x/res)/2;
}
return (int)res;
}
};