69. Sqrt(x)

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

solution

• 二分法

  • 由于输入与输出都是整数，因此小数被truncated

class Solution:
    def mySqrt(self, x: int) -> int:
        # 左闭右闭     
        l = 0
        r = x  # 注意和列表差异，len(nums)-1, 但sqrt当x=0或1时要包含
        while l <= r:
            mid = l + (r - l) // 2
            if mid * mid == x:
                return mid
            elif mid * mid < x:
                l = mid + 1
            else:
                r = mid - 1
        return r  # 注意输出, 可以输出l-1或输出r

时间复杂度：O(log(x)) 空间复杂度：O(1)

• 牛顿法

时间复杂度：O() 空间复杂度：O()