给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16
输出：true
示例 2：
输入：num = 14
输出：false
提示：
1 <= num <= 2^31 - 1
通过次数140,498提交次数313,365
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-perfect-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
其实也算是二分查找法的一个思想，当使用二分查找法的时候，查找到返回1，没有查找到就返回0。如果对二分查找法不熟的同学可以参考本专栏的二分查找文章https://editor.csdn.net/md/?articleId=123751945
// An highlighted block #include<iostream> #include<vector> using namespace std; vector<int>a; bool seachtarger(int tar) { for(int i=0; i<=tar/2;i++) { a.push_back(i); } for(vector<int>::iterator it = a.begin();it!=a.end();it++) { cout << *it<<" "; } cout << endl; int left = 0; int right = a.size()-1; while(left <= right)//使用的是左右都是闭区间的二分查找法 { int middle = (left+right)/2; if(a[middle]*a[middle]>tar) { right = middle-1; } else if(a[middle]*a[middle] <tar) { left = middle+1; } else { return true; } } return false; } int main() { int target; cin >> target; bool str = seachtarger(target); if(str) { cout << "true" << endl; } else { cout << "false" << endl; } return 0; }
上面这个思路是正确的，但是缺点是用到了额外的vector去存储空间，空间复杂度太高。
#include<iostream> using namespace std; bool isPerfectSquare(int num) { int left = 0; int right = num; while(left<=right) { int middle = (left+right)/2; if((long long)middle*middle > num) { right = middle-1; } else if((long long)middle*middle<num) { left = middle+1; } else { return true; } } return false; } int main() { int n; cin >> n; bool b; b = isPerfectSquare(n); if(b) { cout << "true" << endl; } else { cout << "false" << endl; } return 0; }
