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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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).