这是一道数值处理的题目，和Divide Two Integers不同，这道题一般采用数值中经常用的另一种方法：二分法。基本思路是跟二分查找类似，要求是知道结果的范围，取定左界和右界，然后每次砍掉不满足条件的一半，知道左界和右界相遇。算法的时间复杂度是O(logx)，空间复杂度是O(1)。代码如下：
public int sqrt(int x) {
if(x<0) return -1;
if(x==0) return 0;
int l=1;
int r=x/2+1;
while(l<=r)
{
int m = (l+r)/2;
if(m<=x/m && x/(m+1)<m+1)
return m;
if(x/m<m)
{
r = m-1;
}
else
{
l = m+1;
}
}
return 0;
}这种方法在数值计算中非常常见，还是得熟练掌握。实际面试遇到的题目可能不是对一个整数开方，而是对一个实数。方法和整数其实是一致的，只是结束条件换成左界和右界的差的绝对值小于某一个epsilon（极小值）即可。这里注意一个小问题，就是在java中我们可以用==来判断两个double是否相等，而在C++中我们则需要通过两个数的绝对值差小于某个极小值来判断两个double的相等性。实际上两个double因为精度问题往往是不可能每一位完全相等的，java中只是帮我们做了这种判定。Sqrt(x) -- LeetCode,布布扣,bubuko.com
原文：http://blog.csdn.net/linhuanmars/article/details/20089131