[LeetCode] Sqrt(x) (Java)

Implement int sqrt(int x).

Compute and return the square root of x.

Analysis

We can use binary search for this problem. It could be pretty easy to implement. It’s possible that integer overflows. So in the following code I use long type.

There is another way, which is Newton’s Method. You can check the code here.

Code

public class Solution {
    public int sqrt(int x) {
        long i = 0;
        long j = x / 2 + 1;
        while (i <= j) {
            long mid = (i + j) / 2;
            if (mid * mid == x)
                return (int)mid;
            if (mid * mid < x)
                i = mid + 1;
            else
                j = mid - 1;
        }
        return (int)j;
    }
}

public class Solution {

public int sqrt(int x) {

long i = 0;

long j = x / 2 + 1;

while (i <= j) {

long mid = (i + j) / 2;

if (mid * mid == x)

return (int)mid;

if (mid * mid < x)

i = mid + 1;

else

j = mid - 1;

}

return (int)j;

}

Complexity

The complexity is O(log x).