# 69. Sqrt(x)

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

## solution

* 二分法
  * 由于输入与输出都是整数，因此小数被truncated

```python
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)

* 牛顿法

```python
```

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