二分法实现

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 1:
            return 1
        low = 0
        high = x // 2
        mid = (low+high)//2
        while low <= high:
            if mid ** 2 < x:
                low = mid+1
                mid = (low+high)//2
            elif mid ** 2 > x:
                high = mid-1
                mid = (low+high)//2
            else:
                return mid
        return mid