LeetCode - 367. Valid Perfect Square

时间：2019-03-31 16:18:22 阅读：125 评论：0 收藏：0 [点我收藏+]

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
Output: true

Example 2:

Input: 14
Output: false


使用二分法，时间复杂度为O(n)

 1 public boolean isPerfectSquare(int num) {//二分 my
 2         if(0==num||1==num){
 3             return true;
 4         }
 5         int left =1;
 6         int right = num;
 7         while(left<=right){
 8             int mid = left+ (right-left)/2;
 9             int y = num/mid;
10             if(y==mid&&mid*mid ==num){
11                 return true;
12             }
13             else if(y>mid){
14                 left = mid+1;
15             }
16             else {
17                 right = mid-1;
18             }
19         }
20         return false;
21     }