给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。提示：
- 0 <= x <= 2^31 – 1
解题：
func mySqrt(x int) int {
for i := 0; i <= x; i++ {
if i*i <= x && (i+1)*(i+1) > x {
return i
}
}
return 0
}官方解答：
1.袖珍计算器算法
func mySqrt(x int) int {
if x == 0 {
return 0
}
ans := int(math.Exp(0.5 * math.Log(float64(x))))
if (ans+1)*(ans+1) <= x {
return ans + 1
}
return ans
}2.二分查找
func mySqrt(x int) int {
l, r := 0, x
ans := -1
for l <= r {
mid := l + (r-l)/2
if mid*mid <= x {
ans = mid
l = mid + 1
} else {
r = mid - 1
}
}
return ans
}3.牛顿迭代
func mySqrt(x int) int {
if x == 0 {
return 0
}
C, x0 := float64(x), float64(x)
for {
xi := 0.5 * (x0+C/x0)
if math.Abs(x0-xi) < 1e-7 {
break
}
x0 = xi
}
return int(x0)
}