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:

1
2
Input: 16
Returns: True

Example 2:

1
2
Input: 14
Returns: False

解法1：

基本的binarySearch， 要用一个long来防止overflow.
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public boolean isPerfectSquare(int num) {
        if (num <= 0) {
            return false;
        }
        long start = 1, end = num;
        while (start + 1 < end) {
            long mid = start + (end - start) / 2;
            long temp = mid * mid;
            if (temp < num) {
                start = mid;
            } else if (temp > num) {
                end = mid;
            } else {
                return true;
            }
        }
        if (end * end == num || start * start == num) {
            return true;
        }
        return false;        
    }
}