java - 判断给定的数是否是完全平方数？

Question

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;
      //  System.out.println(l + " " + r + " " + mid + " " +n);
        if(mid*mid == n) return true;
        else if(mid*mid>n) return searchBinary(l, mid-1, n);
        else return searchBinary(mid+1, r, n);
    }
    return false;
}

我的代码 n=808201 失败

我不明白为什么它不起作用。这段代码对我来说看起来不错。有什么建议吗？

Answer 1

因为mid * mid超出了int范围。

对于 n=808201，在 mid = 300325 处失败，更改为长值

public static boolean isPerfectSquare(int n) {
        int l=1, r=n;
        if(r==l) return true;
        return searchBinary(l, r, n);
    }
    public static boolean searchBinary(long l, long r, int n){
        if (l > r) {
            return false;
        }
        long mid=(r + l) >> 1;
        //  System.out.println(l + " " + r + " " + mid + " " +n);
        if(mid*mid == n) return true;
        else if(mid*mid>n) return searchBinary(l, mid-1, n);
        else return searchBinary(mid+1, r, n);
    }