69. x 的平方根

https://leetcode-cn.com/problems/sqrtx/

解法一:

二分,直到找到i == x/i的i为止

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

最后更新于