LeetCode 367、有效的完全平方数

367、有效的完全平方数

1）题目描述

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true

示例 2：

输入：num = 14
输出：false

提示：

• 1 <= num <= 2^31 - 1

2）分析

二分。

需要注意：

• 计算mid的时候为了防止溢出，使用mid=left+(right-left)/2；
• 在判断平方是否等与所给的数字的时候，使用mid==num/mid&&num%mid==0，防止溢出，并且避免非完全平方数存在余数误判。
  

3）C++代码

class Solution {
public:
    bool isPerfectSquare(int num) {
        int left=1;
        int right=num;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(mid==num/mid&&num%mid==0)
                return true;
            else if(mid>num/mid)
                right=mid-1;
            else
                left=mid+1;
        }
        return false;
    }
};