[Leetcode] Sqrt

Implement int sqrt(int x).

Compute and return the square root of x.

Using the idea from Binary Search. Pay attention to some corner case.

    
public int sqrt(int x) {
        if(x < 2)
            return x;
        int i = 1, j = x / 2;
        while(i <= j) {
            int mid = i + (j - i) / 2;
            if(mid == x / mid) 
                return mid;
            else if(mid < x / mid)
                i = mid + 1;
            else 
                j = mid - 1;
        }
        return j;
    }

Another way is to use the Newton method.

    public int sqrt(int x) {
        if(x < 2)
            return x;
        double eps = 0.0000001;
        double oldValue = x, newValue = 1;
        while(Math.abs(oldValue - newValue) > eps) {
            oldValue = newValue;
            newValue = (newValue + x / newValue) / 2;
        }
        if((int)oldValue*(int)oldValue > x)
            oldValue--;
        return (int)oldValue;
    }