Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Using binary search idea, to search between [1, x/2+1].

m*m < x <(m+1)*(m+1)
public int sqrt(int x) {
        if (x<0||x==0) {
            return 0;
        }

        int left = 1;
        int right = x/2 + 1;

        while (left<=right) {
            int middle = left+(right-left)/2;
            if(x/middle>=middle && x/(middle+1)<(middle+1)) {
                return middle;
            } else if (middle<x/middle) {
                left=middle+1;
            } else {
                right=middle-1;
            }
        }

        return 0;
    }