367. 有效的完全平方数

题目链接

分析

什么是完全平方数？如果一个正整数 a 是某一个整数 b 的平方，那麼這个正整数 a 叫做完全平方数。0 也可称为完全平方数。

判断完全平方数的标准是存在正整数 n，且 n 满足 n=x/n 且 0 =x%n。这个跟 69. x 的平方根 中的算数平方根的概念是不一样的。

有两点需要注意

• 首先题目中说了 num 从 1 开始，因此排除 0
• 在判断平方相等的时候，要同时判断除数和余数，middle == num/middle 而且 num % middle == 0，middle 才是其平方根，如果余数不为 0，说明还是小了，需要向右移动左边界。

这个题跟 69. x 的平方根 非常像，而且比 69 题简单，因为 69 题求的是平方根的整数部分，所以 mid <= target/mid 的时候 mid 就可能是我们的平方根，但是还需要等待跳出循环，我们才能确定最终的值，但是这个题目不存在这问题，这个题就是要找 mid == target/mid 的时候的值，因此，此题中，只需要 start，end，mid 这三个变量即可。不需要像 34. 在排序数组中查找元素的第一个和最后一个位置 一样用一个额外的对象来保存结果。

解题

public boolean isPerfectSquare(int num) {
    if(num ==0){
        return true;
    }
    int start=1,end=num;
    while(start<=end){
        int mid = start+(end-start)/2;
        if(mid == num/mid){
            // 光这个还不够，还得检查余数，才能保证是完全平方数
            if(num%mid == 0){
                return true;
            }else{
                // 如果余数不为0，那么mid还是小了，还得增加
                start = mid+1;
            }
        }else if(mid > num/mid){
            end = mid-1;
        }else{
            start = mid+1;
        }
    }
    return false;
}

或者精简版

public boolean isPerfectSquare(int num) {
    if(num ==0){
        return true;
    }
    int start=1,end=num;
    while(start<=end){
        int mid = start+(end-start)/2;
        if(mid > num/mid){
            end = mid-1;
        }else{
            start = mid+1;
            if(mid == num/mid && num%mid == 0){
	            return true;
            }
        }
    }
    return false;
}

相关题

704. 二分查找

69. x 的平方根