题目描述：
Implement int sqrt(int x).
Compute and return the square root of x.
实现开根号，并且返回整数值（这个很重要，不是整数的话就有一种方法用不了了）
方法一：二分法，另外由于我们知道开根号的结果肯定小于等于这个数的二分之一，所以还可以做个线性优化，代码如下：
class Solution {
public:
int sqrt(int x) {
long long left=;
long long right=x/+;
long long m=(left+right)/;//注意这里有坑
while(left<=right){
m=(left+right)/;
if(m*m>x){
right=m-;
}
else if(m*m==x){
return m;
}
else{
left=m+;
}
}
return right;
}
};
方法二、牛顿迭代法，具体细节百度之，摘录如下：
设r是的根，选取
作为r的初始近似值，过点
做曲线
的切线L，L的方程为
求出L与x轴交点的横坐标
，称x1为r的一次近似值。过点做曲线
的切线，并求该切线与x轴交点的横坐标
，称
为r的二次近似值。重复以上过程，得r的近似值序列，其中，
称为r的
次近似值，上式称为牛顿迭代公式。
应用到我们的题目里可以得到xi+1= (xi + n/xi) / 2。
于是，代码如下：
class Solution {
public:
int sqrt(int x) {
if (x == ) return ;
double last = ;
double res = ;
while (res != last)
{
last = res;
res = (res + x / res) / ;
}
return int(res);
}
};