有效的完全平方数(Valid Perfect Square)

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true

示例 2：

输入：num = 14
输出：false

提示：

  • 1 <= num <= 2^31 - 1
bool isPerfectSquare(int num){
    for (int i = 0; i < 46341; ++i) {
        if (i*i == num) return true;
        if (i*i >  num) return false;
    }
    return false;
}

暴力！因为46341的平方会超过整数的最大值，因此我们用46341，或者用long long 之类的

bool isPerfectSquare(int num){
    long long d = 2;
    long long s = 1;
    while (s < num){
        s += d + 1;
        d += 2;
    }
    return s == num;
}

奇妙的代码，不过这样还是O(n^(1/2)) 的时间复杂度

bool rangedIsPerfectSquare(int left, int right, int target){
    if (left > right) return false;

    long long mid = left + (right - left)/2;
    if (mid*mid == target) return true;
    if (mid*mid <  target) return rangedIsPerfectSquare(mid+1, right, target);
    return rangedIsPerfectSquare(left, mid, target);
}

bool isPerfectSquare(int num){
    return rangedIsPerfectSquare(1, INT_MAX, num);
}

优秀的时间复杂度 O(log n)