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:
1
Input: 16
2
Returns: True
Copied!
Example 2:
1
Input: 14
2
Returns: False
Copied!

2. Implementation

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

3. Time & Space Complexity

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