Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Solution1: binary search

We can use binary search for this problem. It could be pretty easy to implement. It’s possible that integer overflows. So in the following code I use long type.

The complexity is O(log x). Space complexity is O(1).

public class Solution {
    //二分法
    public int sqrt(int x) {
        if(x < 0)
            return -1;
        if(x == 0)
            return 0;
        
        long l = 1, r = x/2 + 1;
        while(l <= r) {
            long mid = (l + r) / 2;
            if(mid <= x / mid && (mid + 1) > x / (mid + 1))
                return (int)mid;
            else if(mid < x / mid)
                l = mid + 1;
            else
                r = mid - 1;
        }
        
        return (int)r;
    }
}

Solution2:  Newton's method

参考牛顿法-维基百科。一般牛顿法是用数值方法来解一个f(y)=0的方程。

构造f(y)=y^2-x，其中x是要求平方根的数，当f(y)=0时，即y^2-x=0,所以y=sqrt(x),即是要求的平方根。

f(y)的导数f'(y)=2*y，根据牛顿法的迭代公式可以得到y_(n+1)=y_n-f(n)/f'(n)=(y_n+x/y_n)/2。最后根据以上公式来迭代解以上方程。

public int sqrt(int x) {
        if (x == 0) return 0;  
        double lastY = 0;  
        double y = 1;  
        while (y != lastY) {  
            lastY = y;  
            y = (y + x / y) / 2;  
        }  
        return (int)(y); 
    }

Reference: http://blog.csdn.net/linhuanmars/article/details/20089131
Follow up: 返回double

public static double sqrt(double x){ 
	double max = 3200000;
	double min = 0;
	while(max - min > 1e-9){
	    double mid = (max + min) / 2;
	    if(mid * mid > x)
	        max = mid;
	    else
	        min = mid;
	}
	return max;
}