思路：使用二分查找，注意使用mid为右中位数，更新right的时候使用right = mid - 1
class Solution: def mySqrt(self, x: int) -> int: left = 0 right = x // 2 + 1 while left < right: #选取mid的时候慎重，应为右中位数 mid = left + (right - left + 1) // 2 if mid * mid < x: left = mid elif mid * mid > x: right = mid - 1 elif mid * mid == x: return mid # print(mid) return left