LeetCode 69: Sqrt(x) 求根号x(牛顿迭代法和二分查找法)

题目：
Implement int sqrt(int x).
Compute and return the square root of x.

分析：我们平常可能好少会自己去求解某个数的平方根，一般都是直接调用系统提供的函数，其实一般针对问题，并没有直接求解的公式，一般都是通过一个公式多次迭代来无限接近于这个解，这时，这个值就是我们要求的解。
下面我们简要介绍2中方法：牛顿迭代法和二分查找法。

牛顿迭代法想必大家都比较熟悉，就是给定一个初始值，然后一直迭代来逼近方程的解。

比如对于上图，首先给定一个初始值X0，然后，通过这个初始值作函数的切线，与y=0交于一点，横坐标为x1, 在通过点(x1,f(x1))作函数的切线，与y=0交于点(横坐标为x2),这样一直下去，得到xn（若把xn代入方程得到的值与函数实际的值小于某一个很小的阈值，则我们认为xn就是函数的解）

故要求解sqrt(x),即求解sqrt(t)(t=x), 即求函数 f(x)=x2−t=0 的解，我们给初始解赋一个初始值 x0 , 那么我们在点 (x0,f(x0)) 处对曲线作切线， 得到如下方程 y−f(x0)=f(x0)′(x−x0) ，令y=0, 解得 x=x0/2+t/(2x0) , 则迭代的解 x1=x0/2+t/(2x0) ，像这样依次迭代 xn=xn−1/2+t/(2xn−1) , 若 f(xn) 很接近于0(与0的差绝对值小于某个阈值)，这迭代终止， xn 即为函数的解。

int mySqrt(int x) 
{
if(x==0||x==1)
return x;
double x0=x;
double t=x;
    x0=x0/2+t/(2*x0);
while(fabs(x0*x0-t)>0.00001)
    {
        x0=x0/2+t/(2*x0);
    }
cout<<x0<<endl;
return int(x0);
}

另一种方法就是二分查找法了，思路很简单，就不介绍了，直接上代码：

int mySqrt(int x) 
{
if(x==0||x==1)
        return x;
int mid,left=1,right=x;
while(left<right)
    {
mid=left+(right-left)/2;
if(mid>x/mid)
right=mid-1;
else if(mid==x/mid)
            return mid;
else
        {
if((mid+1)>x/(mid+1))
                return mid;
if((mid+1)==x/(mid+1))
                return mid+1;
left=mid+1;
        }
    }
    return (left+right)/2;
}