Solution 1 - Binary Search

Given a positive integer num, return true if num is a perfect square, or false otherwise. A perfect square is an integer that is the square of an integer. You must not use any built-in library function such as sqrt.

Approach: Use binary search over the range [1, num]. At each step, compute the square of the midpoint. If it equals num, return True. If it's greater, search the left half. If it's less, search the right half. If the loop ends without a match, return False.

TimeComplexity: O(\log n)

SpaceComplexity: O(1)

""" 0367.1 - Solution 1 - Binary Search """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def isPerfectSquare(self, num: int) -> bool:
        """Valid Perfect Square Function"""
        left, right = 1, num

        while left <= right:
            mid = left + (right - left) // 2
            sq = mid * mid

            if sq == num:
                return True
            elif sq > num:
                right = mid - 1
            else:
                left = mid + 1

        return False


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().isPerfectSquare(16))   # Expected: True
    print(Solution().isPerfectSquare(14))   # Expected: False
    print(Solution().isPerfectSquare(1))    # Expected: True
    print(Solution().isPerfectSquare(9))    # Expected: True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0367 - Valid Perfect Square

Solution 1 - Binary Search