Leetcode Sqrt(x)

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

分二分法和牛顿迭代法两种解法，详细请看：

http://blog.csdn.net/kenden23/article/details/14543521

二分法：

//2014-2-20 update		
	int sqrt(int x) 
	{
		double e = 0.0000001;
		double a = 0, b = x;
		double m = a + ((b-a)/2);
		double res = m*m - double(x);
		while (abs(res) > e)
		{
			if (res < 0) a = m+1;
			else b = m-1;
			m = a + ((b-a)/2);
			res = m*m - double(x);
		}
		return m;
	}

//2014-2-20 update		
	int sqrt(int x) 
	{
		if (x == 0) return 0;
		double xi1 = x, xi = 1;
		while (int(xi1) != int(xi))
		{
			xi = xi1;
			xi1 = (double(x)/xi + xi)/2;
		}
		return xi;
	}