题目
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
解题
方法一：二分查找
找到 m*m<=x的最大m就行了
class Solution { public: int mySqrt(int x) { long long l=0,r=x; while(l<r){ long long m=(l+r+1)>>1; if(m*m>x){ r=m-1; }else{ l=m; } } return l; } };
方法二：牛顿迭代
class Solution { public: int mySqrt(int x) { if(x==0) return 0; double C=x,x0=x; while(true){ double xi=0.5*(x0+C/x0); if(abs(xi-x0)<1e-7) break; x0=xi; } return (int)x0; } };
