# Question

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.
```

# Solution

Use binary search from 1 to x, and return when `i * i == x`

or binary search yields two adjacent number `i, i + 1`

with `i * i < x < (i + 1) * (i + 1)`

. Then return `i`

.

```
class Solution:
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 0 or x == 1:
return x
min, max = 1, x
while max - min > 1:
mid = (min + max) // 2
mid_2 = mid * mid
if mid_2 > x:
max = mid
elif mid_2 < x:
min = mid
else:
return mid
return min
```