class Solution:
def mySqrt(self, x: int) -> int:
if x <= 1:
return x
lo, hi = 1, x
while lo <= hi:
mid = (lo + hi) // 2
if mid > x/mid: #mid太大,应该缩小
hi = mid - 1
else: #小于或等于
if mid+1 > x/(mid+1): #若后一位就大于,说明结果介于(mid, mid+1)之间
return mid #由于要求截断,返回mid
lo = mid + 1