Valid Perfect Square

Description

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
Returns: True

Example 2:

Input: 14
Returns: False

Tags: Binary Search

解读题意

判断给出的正数是否能开完全平方

思路1

这个题可以转换为查找某一个数并判断其是否具有某种特性，查找就可以利用二分法来做。
1. 循环结点right可以只到num/2即可，不用到num。但可能会造成一种情况，当num=1,所以right=0，进不去循环条件。但num=1是正确的，所以优先排除num=1的情况。

class Solution {

   public boolean isPerfectSquare(int num) {
        if (num <= 0)
            return false;

        if (num == 1)
            return true;

        int left = 1, right = num / 2;
        while (left <= right) {

            long mid = (right + left) >>> 1;
            if (mid * mid == num)
                return true;
            else if (mid * mid < num)
                left = (int) mid + 1;
            else
                right = (int) mid - 1;
        }

        return false;

    }
}

time complexity:O(logn)

leetCode汇总：https://blog.csdn.net/qingtian_1993/article/details/80588941

项目源码，欢迎star：https://github.com/mcrwayfun/java-leet-code