lc069.x的平方根

这个题显然用牛顿迭代法做，但是刚好理了一下二分法，所以用二分写了一下。

这个算法的时间复杂度是O（logN），空间复杂度是O（1）。

python:

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        if x == 1:
            return 1
        first, last = 0, x
        while first < last:
            mid = first + (last - first) // 2
            if mid * mid < x:
                first = mid + 1
            elif mid * mid > x:
                last = mid
            else:
                return mid
        return first - 1

PREVIOUSlc739.每日温度

NEXTlc704.二分查找