Q69 Sqrt(x)

Input: 4
Output: 2

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., 
and since we want to return an integer, the decimal part will be truncated.

class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0 or x == 1:  # 注意 0, 1 这两个特殊的数字
            return x
        low = 0; high = x
        while low <= high:
            mid = (low + high) // 2
            if mid ** 2 <= x < (mid + 1) ** 2:
                return mid
            elif mid ** 2 > x:
                high = mid
            else:
                low = mid
        return 0

a = 8
b = Solution()  
print(b.mySqrt(a))  # 2