367 Valid Perfect Square

367. Valid Perfect Square

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 assqrt.

Example 1:

Input: 16
Returns: True

Example 2:

Input: 14
Returns: False

2. Implementation

(1) Binary Search

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)