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

Complexity

The complexity is O(log x).