题目
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如 sqrt。
示例 1：
输入：16
输出：True
示例 2：
输入：14
输出：False
解题思路
利用二分查找法寻找答案，其初始下限是1， 上限是INT32_MAX的立方根(hardcode)与num的最小值。为了防止溢出，变量使用long类型。
C++解法
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <math.h>
using namespace std;
class Solution {
public:
bool isPerfectSquare(int num) {
long low = 1;
long high = min(num, 46341);
long mid = 0;
long result = 0;
while (low <= high) {
mid = (low + high) / 2;
result = mid * mid;
if (result == num) { return true; }
else if (result < num) { low = mid + 1; }
else { high = mid - 1; }
}
return false;
}
};
int main(int argc, const char * argv[]) {
// insert code here...
Solution solution;
for (int i = 1; i < 100; ++i) {
cout << i << " is " << (solution.isPerfectSquare(i) ? "" : "not ") << "perfect square. " << endl;
}
cout << solution.isPerfectSquare(2147483647) << endl;
return 0;
}
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-perfect-square
