We could use **Binary Search on Result** to get `sqrt(x)`

in `O(logn)`

time.

Code:

```
public int sqrt(int x) {
if (x == 0) {
return 0;
} else if (x < 0) {
return -1;
}
long start = 1, end = x, mid = -1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
long square = mid * mid;
if (square == x) {
return (int) mid;
} else if (square < x) {
start = mid;
} else {
end = mid;
}
}
if (start * start <= x) {
return (int) start;
}
if (end * end <= x) {
return (int) end;
}
return -1;
}
```

Thanks to @StefanPochmann, I get to know the Newton's Method. Here is the post 3-4 short lines, Integer Newton, Every Language as a note for me.