69. sqrt(x)

class :
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        for i in range(x+1):
            if (i+1)**2 > x:
                return i

class :

    
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """

        def dfs (start,end):

            # int(float) method, 去小数点后面的数
            mid = int((start + end)/2)

            if mid **2 > x:
                return dfs(start,mid-1)
            else:
                if (mid+1) ** 2 > x:
                    return mid
                else:
                    return dfs(mid+1,end)

        return dfs(0,x)