[LeetCode]sqrt(x) (완료)

[yeonghwanjeon]

• 문제 링크

• 문제 풀이

  • Binary search 문제 : O(log n)으로 가능

    
    class Solution(object):
    def mySqrt(self, x):
    """
    :type x: int
    :rtype: int
    """
    if x == 1 : return 1
    
    mid = x // 2
    bm = 0
    while True :
        if mid ** 2 <= x and (mid + 1) ** 2 > x :
            return mid
    
        if mid ** 2 > x :
            bm = mid
            mid = bm // 2
        else :
            mid = (mid + bm) // 2
    
    return mid