给你一个非负整数?x?，计算并返回?x?的?算术平方根?。
由于返回类型是整数，结果只保留?整数部分?，小数部分将被?舍去 。
注意：不允许使用任何内置指数函数和算符，例如?pow(x, 0.5)?或者?x ** 0.5?。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1题解：
1.二分法
本质还是二分法，从0-x找符号条件的数。
因为0和1比较特殊，平方就是本身，所以额外判断。
其他的数就用二分，如果平方大于x了，那么要缩小，往左边缩小。这种是肯定不满足的。
第二种情况，就是正好等于x，这种概率低。
第三种情况，比x小，这种情况最多，可能满足情况，只需要再缩范围，如果下一次缩圈之后比x大了，那么这个就是满足条件的数。
需要注意的就是要开long long，我最开始用int就爆了测试点，因为最后测试点里有数据超int了，都开成long long就没问题了。
class Solution {
public:
int mySqrt(int x) {
if(x==1||x==0) return x;
long long low = 1,high = x,res = -1;
while(low <= high){
long long mid = (low+high)/2;
if((long long)mid*mid <= x){
res = mid;
low = mid+1;
}else{
high = mid-1;
}
}
return res;
}
};2. 牛顿迭代法
本质是泰勒级数，需要证明的朋友可以去知乎找找，太复杂了我这里不做多证明。
class Solution {
public:
int mySqrt(int x) {
if (x == 0) return 0;
double last=0;
double res=1;
while(res!=last)
{
last=res;
res=(res+x/res)/2;
}
return int(res);
}
};