1

我遇到了一种算法，可以在 O(logN) 时间内判断给定数字是否是完美平方。

这是这个想法的实现（JAVA）。

public boolean isPerfectSquare(long x) {
        if (x <= 1)
            return true;
        
        long low = 1;
        long high = x;
        long mid = 0;
        while (low <= high) {
            mid = low + (high - low) / 2l;
            if (mid * mid == x)
                return true;
            else if (mid * mid < x)
                low = mid + 1;
            else
                high = mid - 1;
        }
        
        return false;
    }

这适用于像256,808201 等数字但对于像999966000289.

我不知道为什么？

4

1 回答 1

1

正如评论中提到的，问题是中间mid*mid可能溢出。使用无符号类型和“long”或“long long”变体将有所帮助。

但是，对于 和 的初始值low，high的第一个值mid接近x/4。如果x很大，这是平方根的很大过冲。

因此，我们可以通过改进初始估计low和high极限估计来改进可管理数字的范围。

免责声明：堆栈溢出格式不适合长时间分析。我有一个很好的论据，以下是有效的，我在下面包含了其中的一部分，但是完整的分析太长了，无法在这里包含。

bool isPerfectSquare(unsigned long x) {
    if (x <= 1)
        return true;
        
    unsigned long low = 1;
    unsigned long high = x;

    // Improve the low/high limits
    while((low<<1) < (high>>1))
    {
        low <<= 1;
        high >>= 1;
    }

    unsigned long mid = 0;
    while (low <= high) {
        mid = low + (high - low) / 2l;
        if (mid * mid == x)
            return true;
        else if (mid * mid < x)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return false;
}

通过这种修改，mid对于较大的值，初始值要小得多，因此可以处理x较大的值而不会溢出。x

证明下限不会超过平方根并不难，这样做说明了这种方法背后的直觉：

对于一些t, 其中1<=t<2,x=t*2^r对于一些整数, r. 因此：

    sqrt(x) = sqrt(t) * 2^(r/2)

这意味着

    2^(r/2) <= sqrt(x) < 2^(r/2+1)

因此，下限是二进制1移位，直到它到达一半（当r为偶数时）或尽可能接近（当r为奇数时）二进制表示中最左边的 1 位x。这正是while-loop 中发生的事情。

表明这high确实是 -loop 之后平方根的上限，while需要更长的分析时间。

于 2022-02-04T23:18:55.470 回答