# Sqrt(x)

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

## Analysis

### Binary Search

Typical binary search problem (although better way could be Newton's method)

Tips:

use `mid == x / mid` to avoid overflow

`right` is the closest, since before the last loop, it was left = mid = right

**Newton**

\[\[[https://en.wikipedia.org/wiki/Newton's\_method\](https://en.wikipedia.org/wiki/Newton's\_method\](https://en.wikipedia.org/wiki/Newton's\_method\]%28https://en.wikipedia.org/wiki/Newton's\_method)\\](https://en.wikipedia.org/wiki/Newton's_method]\(https://en.wikipedia.org/wiki/Newton's_method]\(https://en.wikipedia.org/wiki/Newton's_method]\(https:/en.wikipedia.org/wiki/Newton's_method\)/))

`x_(n+1) = x_(n) - f(x_n) / f'(x_(n))`

For the sqrt(x) function, it's actually:

`f(x) = x^2 - y`

`f'(x) = 2 * x`

Then `x(n+1) = x(n) - [x(n) ^ 2 - y] / [2 * x(n)]`

Simplified:

`x(n+1) = [x(n) + y / x(n)] / 2`

```java
    public int mySqrt(int x) {
        long r = x;
        while (r*r > x)
            r = (r + x/r) / 2;
        return (int) r;
    }
```

## Solution

Using binary search basic template #1

Source: <https://leetcode.com/problems/sqrtx/discuss/25047/A-Binary-Search-Solution/24042>

* The sequence`1, 2, ... , n`has no duplication.
* Near the very end, closest step, before`while`loop,`left = mid = right`.
* In`while`, If`mid < sqrt(x)`,`left = mid + 1`executed,`right`pointer is not moving, and`right`is the answer.
* If`while`, If`mid > sqrt(x)`,`right = mid - 1`executed,`right`pointer shifts left`1`, closest to`sqrt(x)`,`right`is also the answer.

```java
public int mySqrt(int x) {
    int left = 1, right = x;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (mid == x / mid) {
            return mid;
        } else if (mid < x / mid) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;
}
```