# 69. Sqrt(x)
#### Difficulty: Easy
link: https://leetcode.com/problems/sqrtx/

### 1. Binary Search
#### $O(log(x))$ runtime, $O(1)$ space
套用Binary Search模板。

題目要求truncate小數點，所以binary search要找比x平方根還大一點的數，最後再減1。

題目給定$x$範圍是$0$到$2^{31}-1$，下界設為0，考慮$x$不超過$2^{32}$，故上界設為$\sqrt{2^{32}}=2^{16}=64 * 1024$，再考慮邊界條件$x=0$和$x=1$的情況，進入binary search後回傳left-1，所以設定上界為$min(..., x+1)$。

##### python

class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, min(64 * 1024, x + 1)
        
        while left < right:
            mid = left + (right - left) // 2
            if mid * mid > x:
                right = mid
            else:
                left = mid + 1
        
        return left - 1

<font color="#00AB5F ">Accepted</font>
Runtime: **79 ms**, faster than **32.09%** of Python3 online submissions for Sqrt(x).
Memory Usage: **13.8 MB**, less than **56.60%** of Python3 online submissions for Sqrt(x).

###### tags: `leetcode`