LeetCode力扣有效的完全平方数
程序员文章站
2023-12-26 15:40:03
...
不能使用内置函数sqrt等等
正数num的平方根位于1到num/2之间,可以考虑使用二分查找,不过定义一些变量时需要使用long long int。
class Solution {
public:
bool isPerfectSquare(int num) {
if(num==1)
return true;
else
{
return binarySearch(1,num/2,num);
}
}
bool binarySearch(long long int left,long long int right,int num)
{
long long int mid;
while(left<=right)
{
mid=(left+right)/2;
if(mid*mid==num)
return true;
else if(mid*mid<num)
{
left=mid+1;
}
else
{
right=mid-1;
}
}
return false;
}
};