x的平方根

题目

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

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

示例 1:

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

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

思路

• 程序思路,一直加一进行判断
• 数学思路,尝试值初始值为x,然后每次变为(尝试值/2+尝试值)/2

代码

• 程序思路代码

public int mySqrt(int x) {
        if(x == 0){
            return 0;
        }else if(x == 1){
            return 1;
        }
        int y = 1;
        int sum = y * y;
        
        while (x > sum){
            y++;
            if(y == 46341){
                return 46340;
            }
            sum = y * y;
            if(sum == x){
                return y;
            }
        }
        return y-1;
    }

• 数学思路

    public int mySqrt(int x) {
        if (x == 0) return 0;
        long sqrt = x;
        while (sqrt * sqrt > x){
            sqrt = (sqrt + x / sqrt) / 2;
        }
        return (int)sqrt;
    }