Implement int `sqrt(int x)`

.

Compute and return the square root of *x*.

**Example**

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

**Challenge**

O(log(x))

Solution: Binary search O(log(x)). Remember to use Long during computation

public int sqrt(int x) { // find the last number which square of it <= x long start = 1, end = x; while (start + 1 < end) { long mid = start + (end - start) / 2; if (mid * mid <= x) { start = mid; } else { end = mid; } } if (end * end <= x) { return (int) end; } return (int) start; }