问题：为intsqrt(intx)实现整数平方根
有很多方法可以计算整数平方根。但是如果你不打扰，你总是可以欺骗编译器（在线判断），但不要在你的面试中这样做！
作弊方式：
好吧，大多数编程语言都有用于浮点数（单精度或双精度）的sqrt，我们可以简单地编写：
#includemath.h
classSolution{
public:
intsqrt(intx){
//addstd::namespacetodistinguishfromcurrentsqrt()
return(int)std::sqrt(x);
}
};
或者
publicclassSolution{
publicintsqrt(intx){
return(int)Math.sqrt(x);
}
}
或者
（
）
#includemath.h
classSolution{
public:
intsqrt(intx){
return(int)pow(x,0.5);
}
};
穷举搜索：
人们可能会很快想出一个蛮力搜索。我们只需要尝试从1开始的数字，直到这个数字的平方大于输出。
#includemath.h
typedefunsignedlonglongULONG;
classSolution{
public:
intsqrt(intx){
ULONGa=1;
while(a*a=x)a++;
return--a;
}
}
请注意，我们定义了一个unsignedlonglong类型来保存a*a的中间结果，这样结果就不会溢出（对于32位整数来说太大了）。
好吧，以上似乎不太可能在网上判断中接受。但令人惊讶的是，这是一个公认的解决方案。这是为什么？的int类型是32位有符号整数，其给出的最大值2^31-1=。这个的平方根只是.9，这意味着最多次迭代，我们有正确的整数根。这在现代处理器中是微不足道的，可以在百万秒内完成。
改进：
我们注意到a*a很费计算资源，如何摆脱它？
因此，我们只需将2添加到变量delta并将其添加到当前变量a即可得到a+1的平方。
#includemath.h
typedefunsignedlonglongULONG;
classSolution{
public:
intsqrt(intx){
ULONGa=1;
ULONGdelta=3;
while(a=x){
a+=delta;//(a+1)^2
delta+=2;
}
returndelta/2-1;
}
}
上述改进去除了乘法并仅使用加法，这通常在一些时间不是关键问题的PC板中实现。
二分查找：
上面的算法复杂度是O(n)并且当给定的整数很大时它仍然很慢。二分查找可以将其缩短为
二分搜索是最重要的算法之一，为了使其工作，它需要连续的搜索空间（例如数字排序）
在整数平方根的域中，我们可以很容易地发现：
小于
任何给定的非负整数。
#includemath.h
typedefunsignedlonglongULONG;
classSolution{
public:
intsqrt(intx){
ULONGl=0,r=x;
while(l=r){
ULONGmid=l+(r-l)/2;//(l+r)/2;
ULONGmidmid=mid*mid;
//checkifxfallsinto[mid^2,(mid+1)^2)
if((midmid=x)(x(mid+1)*(mid+1)))returnmid;
if(midmidx){
r=mid-1;
}else{
l=mid+1;
}
}
}
}
使用二分搜索，每次迭代都会将搜索空间缩小到一半。的中期=（L+R）/2可能溢出所以我们可以使用中间=1+（R-1）/2来完成相同的事情。
牛顿法：
二分搜索是一个很大的改进，但找到解决方案仍然太慢。现代处理器实现了硬件平方根算法，其中大部分基于牛顿方程：
正如我们所看到的，随着牛顿方程的每次迭代，我们找到了更接近的根
我们有初步的猜测
。
例如，
牛顿法收敛很快，被认为非常有效。
#includemath.h
typedefunsignedlonglongULONG;
classSolution{
public:
intsqrt_newton(intx){
if(x==0)returnx;
doubledividend=x;
doubleval=x;
doublelast;
do{
last=val;
val=(val+dividend/val)*0.5;
}while(abs(val-last)1e-9);//precision
return(int)val;
}
}
我们
用最后一次检查当前迭代
，如果差异小于例如1e-9(EPSILON)，那么我们认为我们已经获得了所需的精度。
另一个类似的问题是检查给定的整数是否是有效的完美平方。