C++ 刷题坑: 二分查找也没有那么容易写出来

最近在刷题, 刷了一道比较简单的二分搜索, 但是却让我刷了好几次才过(果真是很久没刷能力立马下降许多)

题意就是不允许使用 sqrt 或者 pow 之类的函数来判断一个整数是否是平方数. 比如 4, 16, 64, 25 就是平方数而 3, 7, 11 不是.

很容易想到可以用二分搜索来解决, 算法复杂度是 O(log n), 答案如下:

typedef unsigned long long INT64;
 
class Solution {
public:
    /**
     * @param num: 一个正整数
     * @return: num 是否是个完全平方数
     */
    bool isPerfectSquare(int num) {
        int low = 1;
        int high = num;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            auto midmid = (INT64)mid * mid;
            if (midmid == num) {
                return true;
            }
            if (num < midmid) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
};

typedef unsigned long long INT64;

class Solution {
public:
    /**
     * @param num: 一个正整数
     * @return: num 是否是个完全平方数
     */
    bool isPerfectSquare(int num) {
        int low = 1;
        int high = num;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            auto midmid = (INT64)mid * mid;
            if (midmid == num) {
                return true;
            }
            if (num < midmid) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
};

用C++来写有几个坑: