###### tags: `leetcode` `easy` `Math` `Binary Search`
# [69. Sqrt(x)](https://leetcode.com/problems/sqrtx/)

## Description

Given a non-negative integer `x`, return *the square root of* `x` *rounded down to the nearest integer*. The returned integer should be **non-negative** as well.

You **must not use** any built-in exponent function or operator.

- For example, do not use `pow(x, 0.5)` in c++ or `x ** 0.5` in python.

## Examples
### Example 1:

**Input**: x = 4
**Output**: 2
**Explanation**: The square root of 4 is 2, so we return 2.

### Example 2:

**Input**: x = 8
**Output**: 2
**Explanation**: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

## Constraints:

- $0 \leq x \leq 2^{31} - 1$

## Code

int mySqrt(int x) {
    int pre = x / 2, now = x / 4;
    if (x == 1)
        return 1;
    // 4 is the largest number that (num^2)/4 <= num
    if (x <= 4)
        return x / 2;
    while (1) {
        // if search window cross the answer, the upper range is the answer
        if (x / pre >= pre)
            return pre;
        // using binary search concept to find the range that sqrt exist
        if (x / now < now || (x / now == now && x % now)) {
            pre = now;
            now /= 2;
        }
        // if we find the range search form both ended
        else {
            pre--;
            now++;
        }
    }
}

## Complexity

|Space |Time |
|- |- |
|$O(1)$|$O(log(N))$|

## Result

- Runtime : 36 ms, 17%
- Memory usage : 5.7 MB, 31.62%