69. Sqrt(x)

69. Sqrt(x)

 

통과는 하지만, 쫌 오래 걸림

class Solution:
    def mySqrt(self, x: int) -> int:
        i = 0
        while(i>=0):
            if (i*i == x):
                return i
            elif (i*i > x):
                break
            
            i+=1

        return i-1

 

https://youtu.be/zdMhGxRWutQ?si=DRszQKJf3yNpiTyt

 

바이너리 써치로..

class Solution:
    def mySqrt(self, x: int) -> int:
        # 바이너리 써치로. 이진 탐색
        l, r = 0, x
        res = 0

        while l<=r:
            # mid = (l+r) // 2 <-- 이거는 오버플로어 될수도 있다고 함
            mid = (l + (r-l) //2)            

            if mid**2 == x:
                return mid
            elif mid**2 < x: # 오른쪽으로
                l = mid +1
                res = mid # 가능성 있는 값을 업데이트
            else:
                r = mid -1

        # r < l 인 상태니깐
        # l 은 아마도 넘어가는 범위일듯 
        # return r 해도 맞음
        return res