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

Returns: True

Example 2:

Input: 14

Returns: False

注意審題：以前做過是否為2的平方數，我記得解法是如下，直接統計1的個數。

//如果是2的某次方的值，那麼肯定二進制中的數字就隻有一個，
        /*審題錯誤不一定是二的某次方
         * int cou = Integer.bitCount(num);
        if (cou==) {
            return true;
        }
        return false;*/
           

接下來我的AC答案其實很容易想到：

for (int i = ; i <= num/+; i++) {
            if (i*i == num) {
                return true;
            }
        }
        return false;
           

但是速度是相當的慢；Just beats 2.04%

之後看了别人的答案，時間複雜度為logn

public boolean isPerfectSquare(int num) {

int low = 1, high = num;
    while (low <= high) {
        int mid = (low + high) /2;
        if (mid * mid == num) {
            return true;
        } else if (mid * mid < num) {
            low = (int) mid + 1;
        } else {
            high = (int) mid - 1;
        }
    }
    return false;
}