[LeetCode] Valid Perfect Square 파이썬 (Binary Search, +Lower Bound)

이렇게 풀어도 되지만 사실은

Binary Search 를 사용하는 것이 문제의 의도.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        sq = num ** 0.5 
        
        if sq == int(qs): 
            return True
        return False

---

Binary Search

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

elif랑 else문은 left, right을 mid에서 +1, -1 이동 시키는 것

return 조건은 mid * mid == num 일때 return

 

Binary Search 할때 while 문을 잘 생각해야 하는데

여기서는 최대, 최소 요구사항이 없기 때문에 상관이 없다.

---

++ Lower Bound

위의 조건과는 다르게 equal 사인이 없다.

# Lower Bound
def LowerBound(arr, start, end, n):
    while start < end: # this is differ from normal BinarySearch
        mid = (start + end) // 2

        if arr[mid] < n: # if found array is less than -> search right side
            start = mid + 1
        else: 
            end = mid
            # greater or equal to -> not -1 that normally do
            # make end position as equal to mid
            # since we need to find greater value than target not equal
    return end

참고 문제 : www.acmicpc.net/problem/12015