# 367 Valid Perfect Square

## 367. [Valid Perfect Square](https://leetcode.com/problems/valid-perfect-square/description/)

## 1. Question

Given a positive integernum, write a function which returns True ifnumis 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. Implementation

**(1) Binary Search**

```java
class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 1) {
            return false;
        }

        long start = 1, end = num, mid = 0;

        while (start + 1 < end) {
            mid = start + (end - start) / 2;

            if (mid * mid == num) {
                return true;
            }
            else if (mid * mid < num) {
                start = mid + 1;
            }
            else {
                end = mid - 1;
            }
        }

        if (start * start == num || end * end == num) {
            return true;
        }
        else {
            return false;
        }
    }
}
```

## 3. Time & Space Complexity

**Binary Search:** 时间复杂度O(logn), 空间复杂度O(1)