367. Valid Perfect Square
题意：不用api，判断一个整数是否是平方数。
开始的想法是直接用二分法判断是否是平方数。
错误的代码：
1 public boolean isPerfectSquare(int num) { 2 // binary search 3 int i=0; 4 int n=num; 5 while(i<=n){ 6 int mid=i+(n-i)/2; 7 int square=mid*mid; 8 if(square==num) return true; 9 else if(square<num){ 10 i=mid+1; 11 } 12 else { 13 n=mid-1; 14 } 15 } 16 return false; 17 }
第7行相乘会溢出，并且测试超时（应该就是溢出导致循环一直运行下去了）。
修改为以下代码，测试通过。
1 public boolean isPerfectSquare(int num) { 2 // binary search 3 int i=1; 4 int n=(num>>1)+1; 5 while(i<=n){ 6 int mid=i+(n-i)/2; 7 long square=(long)mid*mid; 8 if(square==(long)num) return true; 9 else if(square<(long)num){ 10 i=mid+1; 11 } 12 else { 13 n=mid-1; 14 } 15 } 16 return false; 17 }
原文：http://www.cnblogs.com/shizhh/p/5694005.html