sqrtx

"""
https://leetcode.com/problems/sqrtx/description/
"""


class (object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        >>> s = Solution()
        >>> s.mySqrt(4)
        2
        >>> s.mySqrt(0)
        0
        >>> s.mySqrt(8)
        2
        >>> s.mySqrt(1)
        1
        >>> s.mySqrt(2147395600)
        46340
        """
        if 0 <= x < 1:
            return 0
        elif x == 1:
            return 1
        else:
            
            x0 = x // 2
            while True:
                # x**2/4 > x
                if x0**2 <= x:
                    return x0
                x0 = int((x0 + x / x0) / 2)