没有任何内置函数的平方根？

Question

问题是求整数 0 的平方根 <= n <= 2^31 - 1 and round it down to the nearest integer.

这是我的工作功能：

int mySqrt(int x) {
    if (x == 0) {
        return x;
    }
    
    int k;
    double x1, x2;

    x2 = x / 2;
    
    while(true) {
        x1 = (x2 + (double)x / x2) / 2;
        if (fabs(x1 - x2) < 0.00001) {
            break;
        }

        x2 = x1;
    }

    return (int)x1;
}   

如果有人知道为什么发生“超出时间限制”错误，请告诉我。

Answer 1

mySqrt 的输入和输出都是整数，因此最好在函数内保留整数数学。由于使用浮点运算，完成该功能的时间大大增加。负数也可能导致问题，因为您无法计算负数的平方根。

这是一个按指定工作的示例，仅使用整数数学：

int mySqrt(int x) {
    if (x < 0) { return -1; } // Illegal
    if (x < 2) { return x; }  // Handle 0 and 1

    int x1 = x;
    int x2 = x / 2;
    while (x1 > x2) {
        x1 = x2;
        x2 = ((x / x1) + x1) / 2;
    }
    return x1;
}