Java判断完全平方数代码在n=808201时失效，求排查建议

嘿，我立马就发现你的代码问题出在整数溢出上了！这是二分查找判断完全平方数时非常常见的坑，咱们一步步拆解：

为什么n=808201会失败？ #

你的代码里用mid*mid来和n比较，但Java的int类型最大值是2^31-1（也就是2147483647）。当你处理n=808201时，二分查找的初始右边界r=808201，第一次计算mid是(1+808201)/2=404101，这时候404101*404101的结果远远超过了int的最大值，会发生溢出——结果变成一个负数。这时候你的判断条件mid*mid >n就会因为负数小于808201而不成立，代码错误地去搜索右半部分，最终找不到正确的平方根899，返回false。

解决办法（三种可选方案） #

方案1：用long存储乘积避免溢出 #

最简单的修复方式是把mid的平方计算转换为long类型，这样就不会超出范围：

public boolean isPerfectSquare(int n) {
    int l = 1, r = n;
    if (r == l) return true;
    return searchBinary(l, r, n);
} 

public boolean searchBinary(int l, int r, int n) {
    if (r > l) {
        int mid = l + (r - l) / 2;
        // 将mid转为long后再计算平方，避免溢出
        long square = (long) mid * mid;
        if (square == n) {
            return true;
        } else if (square > n) {
            return searchBinary(l, mid - 1, n);
        } else {
            return searchBinary(mid + 1, r, n);
        }
    }
    return false;
}

方案2：改用除法判断，完全避免乘法 #

另一种思路是通过mid > n/mid来替代mid*mid >n，这样完全不会涉及到大数乘法：

public boolean isPerfectSquare(int n) {
    int l = 1, r = n;
    if (r == l) return true;
    return searchBinary(l, r, n);
} 

public boolean searchBinary(int l, int r, int n) {
    if (r > l) {
        int mid = l + (r - l) / 2;
        // 用除法避免溢出，注意处理整除的边界情况
        if (mid > n / mid) {
            return searchBinary(l, mid - 1, n);
        } else if (mid < n / mid) {
            return searchBinary(mid + 1, r, n);
        } else {
            // 当mid == n/mid时，还要验证mid*mid是否真的等于n（避免n=10这种情况）
            return mid * mid == n;
        }
    }
    return false;
}

方案3：直接使用long类型变量 #

把二分查找的边界变量l、r、mid都换成long类型，从根源上避免溢出：

public boolean isPerfectSquare(int n) {
    long l = 1, r = n;
    if (r == l) return true;
    return searchBinary(l, r, n);
} 

public boolean searchBinary(long l, long r, int n) {
    if (r > l) {
        long mid = l + (r - l) / 2;
        long square = mid * mid;
        if (square == n) {
            return true;
        } else if (square > n) {
            return searchBinary(l, mid - 1, n);
        } else {
            return searchBinary(mid + 1, r, n);
        }
    }
    return false;
}

额外小提示 #

如果你的代码需要处理n=0的情况，记得在isPerfectSquare开头加个判断：if(n ==0) return true;，因为0也是完全平方数。

内容的提问来源于stack exchange，提问作者Nitin Singhal