Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1: 

1
2
Input: 16
Returns: True

Example 2: 

1
2
Input: 14
Returns: False

思路

判断一个数是否为完全平方数。如果利用2~num的数对num进行求余，算法复杂度是O(n)，其实很有可能会超时。要防止超时，使用二分法进行搜索，会显得比较省时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if (num == 1):
            return True
        high = num
        low = 0
        mid = 0
        while (mid != ( high + low ) / 2) :
            mid = ( high + low ) / 2
            if mid * mid > num:
                high = mid  + 1
            elif mid * mid == num:
                return True
            else:
                low = mid
        return False