自己写果然一上来就超时啊, 看了水中的鱼的解体报告, 可以用二分法, 也可以用牛顿迭代法, x = (x + a / x) / 2, 膜拜大神啊

class Solution:
    # @param x, an integer
    # @return an integer
    def sqrt(self, x):
        left = 0
        right = 46340 # sqrt(C MAX_INT 2147483647)=46340.950001
        while left <= right:
            mid = (left + right) / 2
            if mid ** 2 <= x < (mid + 1) ** 2:
                return mid
            elif x < mid ** 2:
                right = mid - 1
            else:
                left = mid + 1

class Solution:
    # @param a, an integer
    # @return an integer
    def sqrt(self, a):
        x = 1
        new_x = (x * 1.0 + a * 1.0 / x) / 2
        while int(x) != int(new_x):
            x = new_x
            new_x = (x * 1.0 + a * 1.0 / x) / 2
        return int(x)