69. x的平方根

题目描述：

给你一个非负整数 x ，计算并返回 x 的算术平方根 。

由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

题目分析：

对于此题我们要明白一个数学规律：一个正数x的平方根是>= x / 2，有了这个规律我们可以想到二分法来选择做此题。

1. 二分法

int mySqrt(int x){
   int left=1;
   int right=x/2+1;       //这里本身是可以为x/2但因为有0这个因素的考虑，因此right+1
   while(left<=right){
       int mid = left+((right-left)>>1);//这里等价于 mid = （right+left）/2 ，这里这样写是避免溢出
       if(mid>x/mid){
           right=mid-1;
       }
       else if(mid<x/mid){
           left=mid+1;
       }
       else{
           return mid;  //条件满足则返回
       }
   }
   return right; //最后要返回的是零向取整的值，因此返回right
}

2. 牛顿迭代法

思路

牛顿迭代法是一种可以用来快速求解函数零点的方法。

f(y) = y^2 - C

将C换成 引入值，则y就是所求值.

代码如下：

int mySqrt(int x){
  
  if(x==0){      //特殊情况
      return 0;
  }
    double c=x;
    double x0=x;
    while(1){
        double x1 = (x0+c/x0)*0.5;
        if(fabs(x0-x1)<1e-7){       //满足两者距离小于e*10^-7次方退出
            break;
        }
        x0=x1;
    }
    return (int)x0;      //返回取整值
}