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

Example 2:

Input: 14Output: 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     }

 

相关题

一个数的平方根 LeetCode69