(二分查找,牛顿迭代)计算x的平方根

最简单的暴力法（太菜了，只能写这种简单的。。）

func mySqrt(x int) int {
	for i := 0; i <= x/2; i++ {
		if i*i <= x && (i+1)*(i+1) > x {
			return i
		}
	}
	return 1
}

这个其实就是遍历，然后比对（这里是利用了题目只要求我们双整数的条件，所以这样才可以的）

袖珍计算器法（利用指数函数和对数函数来进行计算）

这里其实利用了数学里面的换低公式。（数学，永远的神。。）

虽然这个方法很巧妙，但是有缺点：（所以我们在计算后需要验证）

实验代码如下：

// 解法二： 巧妙利用换底公式：指数函数 exp 和对数函数 ln 代替平方根函数的方法
// 时间复杂度 1  空间复杂度也是1
func mySqrt(x int) int {
	if x == 0 {
		return 0
	}
	// 这里实际上就是在计算这个换底公式
	ans := int(math.Exp(0.5 * math.Log(float64(x))))
	// 因为这个计算存在误差，所以我们需要分别判断ans 和ans+1 那个才是正确的答案
	if (ans+1)*(ans+1) <= x {
		return ans + 1
	}
	return ans
}

二分查找

这个原理其实很简单，就是利用二分查找快速缩小范围，避免我之前那种暴力算法耗时。。。下次我注意。。

// 解法三： 二分查找，我们可以通过二分查找快速缩小我们查找的范围
// 时间复杂度o(logx) 空间复杂度O(1)
func mySqrt(x int) int {
	// 我们这里设置l是下界，r为上界
	l, r := 0, x
	// 先假设我们的结果为-1(避免与正确答案冲突)
	ans := -1
	// 循环的时候要保证l始终小于r
	for l <= r {
		// 计算中位数,获取中间的值
		mid := l + (r-l)/2
		// 当这个中位数小于x的时候，我们把下界置为中位数+1（因为结果肯定比中位数要大）
		if mid*mid <= x {
			// 这里我们顺便记一下结果，因为最后退出的时候是返回ans的
			ans = mid
			l = mid + 1
		} else {
			// 否则就说明中位数太大了，我们这里把上界置为中位数-1
			r = mid - 1
		}
	}
	return ans
}