Easy！
题目描述：
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
解题思路：
这道题要求平方根，我们能想到的方法就是算一个候选值的平方，然后和x比较大小，为了缩短查找时间，我们采用二分搜索法来找平方根，这里属于之前总结的LeetCode Binary Search Summary 二分搜索法小结（http://www.cnblogs.com/grandyang/p/6854825.html）中的第三类的变形，找最后一个不小于目标值的数，代码如下：
C++解法一：
class Solution {
public:
int mySqrt(int x) {
if (x <= ) return x;
int left = , right = x;
while (left < right) {
int mid = left + (right - left) / ;
if (x / mid >= mid) left = mid + ;
else right = mid;
}
return right - ;
}
};
这道题还有另一种解法，是利用牛顿迭代法（https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95），记得高数中好像讲到过这个方法，是用逼近法求方程根的神器，在这里也可以借用一下，可参见http://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html，因为要求x2 = n的解，令f(x)=x2-n，相当于求解f(x)=0的解，可以求出递推式如下：
xi+1=xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2
C++解法二：
class Solution {
public:
int mySqrt(int x) {
if (x == ) return ;
double res = , pre = ;
while (abs(res - pre) > 1e-) {
pre = res;
res = (res + x / res) / ;
}
return int(res);
}
};
下面也是牛顿迭代法，写法更加简洁一些，注意为了防止越界，声明为长整型。
C++解法三：
class Solution {
public:
int mySqrt(int x) {
long res = x;
while (res * res > x) {
res = (res + x / res) / ;
}
return res;
}
};