博客

x 的平方根

Sqrt(x)

解

方法一：暴力法

int mySqrt(int x)
{
    int i = 0;

    while((double)i * i <= x){
        i++;
    }

    return i - 1;
}

结果





方法二：二分法

int mySqrt(int x)
{
    int left = 0, right = x / 2 + 1;

    while (left <= right){
        int mid = left + (right - left) / 2;
        double res = (double)mid * mid;

        if(res == x){
            return mid;
        }else if(res < x){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }

    return right;
}

结果





方法三：牛顿迭代法


类似的，可以看LeetCode的367题题解


https://blog.csdn.net/weixin_43443553/article/details/100556682

int mySqrt(int x)
{
    if(x == 0){
        return 0;
    }

    long i = x;

    while (i * i > x){
        i = (i + x / i) / 2;
    }

    return (int)i;
}

结果