# Sqrt(x)

Implement`int sqrt(int x)`.

Compute and return the square root ofx, 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

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

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

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

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

``````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;
}
``````