[leetcode]367. Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Output: true

分析：

判断一个数是不是有效的完全平方数，不能使用类似于sqrt已有的库函数。可以用二分法，先判断n的一半的平方是不是与之相等，若是，直接返回true，若比n小，则将左指针等于mid+1，否则令右指针等于mid-1。若最后left大于right，还没有找到n的正平方根，则返回false。

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