平方根

69. x 的平方根

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

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

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

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

• 0 <= x <= 231 - 1

牛顿迭代法

下面这种方法可以很有效地求出根号 a 的近似值：首先随便猜一个近似值 x，然后不断令 x等于 x 和 a/x 的平均数，迭代个六七次后 x 的值就已经相当精确了。

例如，我想求根号 222 等于多少。假如我猜测的结果为 444，虽然错的离谱，但你可以看到使用牛顿迭代法后这个值很快就趋近于根号 2 了：

( 4 + 2/ 4 ) / 2 = 2.25

( 2.25 + 2/ 2.25 ) / 2 = 1.56944..

( 1.56944..+ 2/1.56944..) / 2 = 1.42189..

( 1.42189..+ 2/1.42189..) / 2 = 1.41423..

设所求的数为a

则下一个更接近使得$f（x） = x^2 - a = 0$的点为$（x1，0）$

$x1 = x - (x^2 - a) / (2x) = x^2 + a / 2x = (x + a/x)/2$

class Solution {
    static int a;
    
    public static int mySqrt(int x){
        a = x;
        if(x == 0) return 0;
        double res = sqrt(x);
        System.out.println(res);
        return (int)res;
    }
    //x = x - (x^2 - a) / (2*x) = x^2 + a / 2*x = (x + a/x)/2
    public static double sqrt(double x){
        double res = (x +  a / x) / 2.0;
        if(res == x){
            return res;
        }else {
            return sqrt(res);
        }
    }
}

二分查找

class Solution {
    public static int mySqrt(int x) {

        int l = 0;
        int r = x;
        while(l <= r){
            int mid = (r - l) / 2 + l;
            if( (long)mid * mid >= x &&  ((long)mid + 1)*(mid + 1) < x){
                return mid;
            }else if((long)mid * mid > x) {
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return 0;
    }

}