69. x 的平方根

easy

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

二分法

x 平方根的整数部分 ans 是满足 k^2^ ≤ x

的最大 kk 值

不多 bb

func mySqrt(x int) int {
	low, high := 0, x
	for low <= high {
		mid := low + (high-low)>>1
		if mid*mid < x {
			if (mid+1)*(mid+1) > x {
                // 找到最后一个小于x的mid
				return mid
			}
			low = mid + 1
		} else if mid*mid > x {
			high = mid - 1
		} else {
			return mid
		}
	}
	return -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
}