## Description

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2


Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.


## Solutions

实现开方的功能，舍去小数部分，只保留整数。

### 1. Binary Search - 迭代

注意最后的结果是 left，还要减 1。

# Time: O(n)
# Space: O(1)
class Solution:
def mySqrt(self, x: int) -> int:
if x < 2:
return x

left, right = 1, x // 2
while left <= right:
mid = left + (right - left) // 2
center = x / mid
if mid == center:
return mid
elif mid > center:
right = mid - 1
else:
left = mid + 1
return left - 1

# 1017/1017 cases passed (28 ms)
# Your runtime beats 90.13 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.6 MB)


当然也可以在更新left时，就不用 mid 加 1，这样最后的结果就不用加 1。同样也可以直接返回 right，这样也不用考虑加 1 的问题。

# Time: O(n)
# Space: O(1)
class Solution:
def mySqrt(self, x: int) -> int:
if x < 2:
return x

left, right = 1, x // 2
while left <= right:
mid = left + (right - left) // 2
x_cmp = mid ** 2
if x_cmp == x:
return mid
elif x_cmp > x:
right = mid - 1
else:
left = mid + 1
return right

# 1017/1017 cases passed (28 ms)
# Your runtime beats 90.13 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.6 MB)


### 2. Binary Search - 递归

class Solution(object):
def binary_search(self, l, r, x):
mid = (l + r) / 2
mid_p = mid ** 2
if mid_p == x:
return mid
elif mid_p < x:
if (mid + 1) ** 2 > x:
return mid
else:
return self.binary_search(mid, r, x)
else:
return self.binary_search(l, mid, x)

def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 1:
return 1
return self.binary_search(0, x, x)
# Runtime: 28 ms, faster than 51.77% of Python online submissions for Sqrt(x).
# Memory Usage: 11.8 MB, less than 29.96% of Python online submissions for Sqrt(x).