Sqrt(x)

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

?

class Solution {
    /**
     * @param x: An integer
     * @return: The sqrt of x
     */
    public int sqrt(int x) {
        if (x == 1) {
        	return 1;
        }
        long t = x/2;
        long a = t;
        while (true) {
        	if (t * t > x) {
        		a = t;
        		t = t/2;
        	} else {
        		if ((t+1)*(t+1) > x) {
        			return (int) t;
        		} else {
        			t = (t+a)/2;
        		}
        	}
        }
    }
}

?