Q:
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 Returns: True
Example 2:
Input: 14 Returns: False
A:
********** 在所有的可能的平方根里,进行二分查找**********class Solution { public: bool isPerfectSquare(int num) { if(num == 1) return true; int low = 2, up = num/2+1; while(low < up) { long mid = low + (up - low) /2; if(mid * mid == num) return true; if (mid * mid > num) { up = mid; }else{ low = mid+1; } } return false; } };
Mistakes:
if we declare:
int mid;
mid * mid would be an int, but can overflow, thus need long.