Sqrt(x)

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

Notes:

1. Binary search on result
2. Use long instead of integer for start, end, middle, to make the end end and middle middle is valid
3. end = x

    public int sqrt(int x) {
        if (x <= 1) {
            return x;
        }

        long end = x;
        long start = 1;

        while(start + 1 < end) {
            long middle = start + (end-start)/2;
            long square = middle * middle;
            if (square < x) {
                start = (int)middle;
            } else if (square > x) {
                end = (int)middle;
            } else {
                return (int)middle;
            }
        }

        if (end*end <= x) {
            return (int)end;
        }

        return (int)start;
    }