LC69 Sqrt(x)

class Solution:
    #time O(lgN)  spoace O(1)
    # main idea: binary search
    def mySqrt(self, x: int) -> int:
        l,r = 0,x
        while l <= r: # add equal to consider edge case 0, 1
            mid = l + (r-l)//2
            if mid**2 <= x< (mid+1)**2:
                return mid
            elif x < mid**2:
                r = mid 
            else:
                l = mid + 1
        return l 

class Solution:
    #time O(lgN)  spoace O(1)
    # main idea: binary search
    def mySqrt(self, x: int) -> int:
        r = x
        while r*r > x:
            r = (r + x/r) // 2 # need to cache r, or it will be slow
        return int(r)