367.有效的完全平方数

https://leetcode-cn.com/problems/valid-perfect-square/

一、暴力

i从1开始递增，每次求i平方是否等于num，直到i平方> num。复杂度O($\sqrt n$ )

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        i = 1
        while i ** 2 <= num:
            if i ** 2 == num:
                return True
            i += 1
        return False

二、二分

只要有序的序列都能二分，已知x^2==num，则x处于[1, num]的区间，在此区间二分即可

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