69sqrt 题目描述
实现 int sqrt(int x) 函数。 计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
例子
Example 1: Input: 4 Output: 2
Example 2: Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842…, and since the decimal part is truncated, 2 is returned.
思想 int(x**0.5) 二分，注意循环的条件以及最后return的值。如果只让left = mid的话，会造成死循环。
class Solution: def mySqrt(self, x): """ :type x: int :rtype: int """ if x < 2: return x left, right = 0, x//2 while left <= right: mid = (left + right) >> 1 if mid * mid == x: return mid if mid * mid > x: right = mid - 1 else: left = mid + 1 return left - 1