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: 16Returns: TrueExample 2:Input: 14Returns: False

我的binary Search 解法：无需变成long

1 public class Solution { 2     public boolean isPerfectSquare(int num) { 3         if (num <= 0) return false; 4         int l=1, r=num/2+1; 5         while (l <= r) { 6             int mid = l + (r-l)/2; 7             if (mid == num/mid && num%mid == 0) return true; 8             else if (mid > num/mid) { 9                 r = mid - 1;10             }11             else l = mid + 1;12         }13         return false;14     }15 }

 

别人三种方法总结：

1. a square number is 1+3+5+7+... Time Complexity O(sqrt(N)) (Credit to lizhibupt, thanks for correcting this).
2. binary search. Time Complexity O(logN)
3. Newton Method. See [this wiki page][1]. Time Complexity is close to constant, given a positive integer.

1 public boolean isPerfectSquare(int num) { 2       if (num < 1) return false; 3       for (int i = 1; num > 0; i += 2) 4         num -= i; 5       return num == 0; 6     } 7      8     public boolean isPerfectSquare(int num) { 9       if (num < 1) return false;10       long left = 1, right = num;// long type to avoid 2147483647 case11     12       while (left <= right) {13         long mid = left + (right - left) / 2;14         long t = mid * mid;15         if (t > num) {16           right = mid - 1;17         } else if (t < num) {18           left = mid + 1;19         } else {20           return true;21         }22       }23     24       return false;25     }26     27     boolean isPerfectSquare(int num) {28       if (num < 1) return false;29       long t = num / 2 + 1; //or t = num as the begining30       while (t * t > num) {31         t = (t + num / t) / 2;32       }33       return t * t == num;34     }