sqrt(x)

gistfile1.java

public int mySqrt(int x) {
        if (x == 0) return 0;
        double last = 0;
        double cur = 1;
        while (cur != last) {
            last = cur;
            cur = ( last + x / last ) / 2;
        }
        return (int) cur;
    }
    
    public int mySqrt(int x) {
        if (x < 0) return -1;
        if (x == 0 ) return 0;
        
        int l = 1, r = x/2 + 1;
        while (l < r) {
            int m = (l+r) / 2;
            if (m <= x / m && m + 1 > x / (m + 1)) {
                return m;
            } else if (m < x / m) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return r;
    }