69. x 的平方根

          题目很简单 给你一个x，返回他的平方根（去掉小数部分），要求不用已有的库函数，

示例 1:
输入: 4
输出: 2

示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。

方法1 暴力迭代

class Solution {
public:
    int mySqrt(int x) {
        if(x<0){
            return 0;
        }
        long long  res=1;  //int 型会超限
        while(1){
            if(res*res>x){
                return res-1;
            }
            res++;
        }
    }
};

方法二 加入了二分的迭代

class Solution {
public:
    int mySqrt(int x) {
        if(x<0){
            return 0;
        }
        if(x==1){    //1需要特判。因为上下限再[0,1],折半永远也到不了1，
            return 1;
        }
        double ul=x,dl=0.0,mid=0;  //设置上下限
        while(abs(mid*mid-x) > 0.01){
            mid= dl+(ul-dl)/2;
            if(mid*mid>x){
                ul=mid;
            }else{
                dl=mid;
            }
        }
        return int(mid);
    }
};

方法三 利用牛顿法公式迭代

class Solution {
public:
    int mySqrt(int x) {
        double res=1.0,err=0.001;
        if(x<0){
            return 0;
        }
        while(abs(res*res-x)>err){
            res=(res + x/res)/2;
        } 
        return int(res);
    }
};