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

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)\)

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

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

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