題目： LeetCode - 367. Valid Perfect Square

題目說明

給一個整數，求此數是否是完全平方數。( 開根號後還是整數 )
※ 題目要求不要使用包含在 Library 內的 Function，如 sqrt()… 等等。

解題思路

使用二元搜尋法即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isPerfectSquare(int num) {
        int left = 1, right = num;
        long long mid, squareMid;
        while(left <= right)
        {
            mid = left + (right - left) / 2;
            squareMid = mid * mid;
            if(squareMid == num)
                return true;
            else if(squareMid > num)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return false;
    }
};