求解一个整数的平方根最简单的办法就是用库函数。
但是如何不用库函数就求解呢？
1. 二分法
我们都知道5的平方根是2.236。如果要求对平方根取整，那么就是2，我们的目的就是在{1，2，3，4，5}这样一个数组中找到2。
这是一个典型的查找的需求，我第一时间想到的查找算法就是二分法。
设left=1，right=5，那么第一趟的mid=3，mid^2=9，大于right，因此我们需要将right左移到mid位置来；
第二趟的left=1，right=3，mid=2，此时mid^2 = 4，基本上接近了，因此判断一下(mid+1)^2，发现9>5，这就能断定出5的平方根取整就是2了，直接返回。
下面是代码的实现：
class Solution {
public:
/**
*
* @param x int整型
* @return int整型
*/
int sqrt(int x) {
// write code here
if (x<=0) return 0;
int left = 1;
int right = x;
while (left < right)
{
long mid = (left+right)/2;
if (mid*mid > x)
{
right = mid;
}
else if (mid * mid <= x && (mid+1) * (mid+1) > x)
{
return mid;
}
else
{
left = mid;
}
}
return left;
}
};
二分法的时间复杂度是O(logN)，执行时间也不差：
只用了3ms。
牛顿迭代公式
用牛顿迭代公式求解平方根基本上相当于杀鸡用牛刀。
我们知道平方根实际上就是这样的一个函数：f(x)=x^2-n=0，其实就是求n的过程。
牛顿迭代公式是这样的：
x = x- f(x)/f'(x)
所以带入之前的f(x)，我们就能知道求解平方根不过是求解一个公式罢了：
x = x - (x - n/x)/2，其中n是常数。
写成代码就是这样的：
class Solution {
public:
/**
*
* @param x int整型
* @return int整型
*/
int sqrt(int x) {
// write code here
double x1=1, x2=0;
while (abs(x2-x1)> 1e-8)
{
x2=x1;//x2用于记录上一次迭代的结果
x1 = (x1 + x/x1)/2;
}
return (int) x1;
}
};
这个效率就差点了：
