sqrt(x)@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

Implement int sqrt(int x).

Compute and return the square root of x.

» Solve this problem

刚开始木有理解题意，以为要精确到小数多少位，然后用double输出，但是看到是int的返回值，瞬间简单了不少，只要算出最接近square root的整数就可以了。但是有细节要注意，比如输入的x特别大的时候，假如已经超过了int的最大值，这个时候我们怎么处理？以及如何判断二分查找结束的条件，都是很关键的。

因为整数的乘法可能导致溢出，而溢出的监测和整数加法直接判断是否小于0是不同的，因为整数的乘法有可能多次溢出，当奇书次溢出时是负数，当偶数次溢出时时整数。比如
2147395599 如果用是否小于0来终止二分的话，它的平方根会返回617921965，而不是46339。

所以，二分的终点确定比较重要，在运算中想通过是否小于0来判断溢出，是不可靠的，最好的办法就是在二分之前，要求end小于sqrt(INT_MAX)。sqrt(INT_MAX)是个常量，所以不算cheat。

更快的方法是牛顿迭代，不过这个太偏数学了。详情见http://www.2cto.com/kf/201206/137256.html
牛顿迭代法。顿时觉得神人总是无处不在，那个找出那个最接近sqrt数的那位大哥太神奇了，自己都不明觉厉。哈哈～～

	class Solution {
	public:
	int sqrt(int x) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	int res;
	int begin=0,end, mid=(0+x)/2;
	if(x==1) return 1;
	end= x/2<std::sqrt(INT_MAX)? x/2+1:std::sqrt(INT_MAX);
	mid=(begin+end)/2;
	while(begin<=end)
	{
	int sqr=mid*mid;
	if(mid*mid==x)
	return mid;
	else if(mid*mid>x)
	{
	end=mid-1;
	mid=(begin+end)/2;
	}
	else
	{
	begin=mid+1;
	mid=(begin+end)/2;
	}
	}
	return (begin+end)/2;
	}
	};

view raw sqrt(x) hosted with ❤ by GitHub

	class Solution {
	public:
	int sqrt(int x) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(x<=1) return x;
	int left=0, right=x, mid;
	while( (right-left)>1 )
	{
	mid=left+(right-left)/2;
	if(mid*mid==x)
	return mid;
	else if(mid*mid > x)
	right=mid;
	else
	left=mid;
	}
	return left;
	}
	};

view raw sqrt new version hosted with ❤ by GitHub