Sqrt(x)

Implementint 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 sequence1, 2, ... , nhas no duplication.

• Near the very end, closest step, beforewhileloop,left = mid = right.

• Inwhile, Ifmid < sqrt(x),left = mid + 1executed,rightpointer is not moving, andrightis the answer.

• Ifwhile, Ifmid > sqrt(x),right = mid - 1executed,rightpointer shifts left1, closest tosqrt(x),rightis 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;
}