The C++ Pitfalls of Checking Perfect Square using Binary Search

Write a method to check if a given integer is a perfect square e.g. 4, 9, 16, 25 … you cannot use the sqrt or pow functions.

cplusplus

One solution is to use binary search which has a algorithm complexity of O(log n). Every iteration the search space is narrowed by half.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

typedef unsigned long long INT64;
 
class Solution {
public:
    /**
     * @param num: a positive integer
     * @return: if num is a perfect square else False
     */
    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: a positive integer
     * @return: if num is a perfect square else False
     */
    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;
    }
};

There are a few pitfalls:

• the midmid = mid * mid which could overflow 32-bit and thus you will need a 64-bit integer to hold this.
• mid * mid produces 32-bit result unless you cast it to 64-bit data type.
• (low + high) /2 may overflow 32-bit thus use low + (high – low) / 2.
• while (low <= high) instead of while (low < high), some people may make mistakes when they write this on the whiteboard.
• update the search boundaries via low = mid + 1 and high = mid – 1. Don’t forget about the 1 part.

It is not easy to get it right (implement Binary Search) for the first time.

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

–EOF (The Ultimate Computing & Technology Blog) —