題目描述：

給你一個非負整數 x ，計算并返回 x 的 算術平方根 。由于返回類型是整數，結果只保留 整數部分 ，小數部分將被 舍去 。注意：不允許使用任何內置指數函數和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。示例 1：輸入：x = 4
輸出：2
示例 2：輸入：x = 8
輸出：2
解釋：8 的算術平方根是 2.82842..., 由于返回類型是整數，小數部分將被舍去。提示：0 <= x <= 231 - 1

算法一：

思路：

二分查找，注意數據大小即可

代碼實現：

int mySqrt(long x) {int l=0,r=x,ans=-1;while(l<=r){int mid=l+(r-l)/2;if((long long)mid*mid<=x){//注意數據大小ans=mid;l=mid+1;}else{r=mid-1;}}return ans;
}

算法二：

思路：

質對估算，要判斷值

代碼實現：

算法三：

思路：

牛頓法

代碼實現：

后續補充數學方法，讀者可先自行思考