367. Valid Perfect Square

Description:

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

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

'''
[1] brute force)

code::
def isPerfectSqurare(num):
    for i in range(1,num):
        if i*i==num:
            return True
        elif i*i>num:   # optimization
            break
    return False
    
-T/C: O(n)
-S/C: O(1)
'''

'''
[2] brute force - optimization)

code::
def isPerfectSquare(self, num: int) -> bool:
    i=1
    while i*i<=num:
        if i*i==num:
            return True
        else:
            i+=1
    return False
    
-T/C: O(n^(1/2))
-S/C: O(1)
'''

'''
[3] binary search)

code::
def isPerfectSquare(self, num: int) -> bool:
    left,right=1,num

    while left<=right:
        mid=(left+right)//2
        if mid*mid==num:
            return True
        elif mid*mid>num:
            right=mid-1
        else:
            left=mid+1
    return False

-T/C: O(logn)
-S/C: O(1)
'''

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left,right=1,num
        
        while left<=right:
            mid=(left+right)//2
            if mid*mid==num:
                return True
            elif mid*mid>num:
                right=mid-1
            else:
                left=mid+1
        return False