求平方根 - 逸如风的个人博客

求平方根

方法一：二分

时间复杂度：O(logN)
空间复杂度：O(1)

注意点：

mid*mix > x的时候容易溢出，改成mid > x/mid
mid := (l+r)>>1的时候也容易溢出，改成mid := l + (r-l)>>1

不保留小数

//不保留小数
func Sqrt(x int) int {

	if x <= 0 {
		return 0
	}

	l, r := 1, x-1
	for l <= r {
		mid := l + (r-l)>>1
		if mid > x/mid {
			r = mid - 1
		} else if mid < x/mid {  //Tips:写成x/mid用来确认不会溢出
			l = mid + 1
		} else {
			return mid
		}
	}

	return r
}

保留小数

//返回一个数的整数：保留4位小数
func SqrtToFloat(x int) float64 {
	if x == 0 {
		return 0
	}

	l, r := float64(1), float64(x-1)
	for l <= r {
		mid, _ := strconv.ParseFloat(fmt.Sprintf("%.4f", l+(r-l)/2), 64)
		//保留小数
		if mid > float64(x)/mid {
			r = mid - 0.0001
		} else if mid < float64(x)/mid {
			l = mid + 0.0001
		} else {
			return mid
		}
	}
	r, _ = strconv.ParseFloat(fmt.Sprintf("%.4f", r), 64)
	return r
}

方法二：牛顿迭代

思路：假设我们要求的是整数c的平方根，那么平方根也就是$ x^2 - c = 0 $ 的解(因为曲线是$ y = x_2 - c $)，假设此时我们在$(x_0, {x_0}^2-c)$，也就是曲线上的点

步骤如下：

过该点做切线，这个切线是不断逼近于$ y = x_2 - c $这个曲线与x轴的交点(也就是我们要求的)，切线斜率求导可得为$ 2 * x_0 $，并且经过$(x_0, {x_0}^2-c)$，所以我们切线方程为 $ y = 2x_0*x-x_0^2-c $
切线与x轴交点的横坐标为$ \frac{x_0}{2} + \frac{c}{2x_0} $，下次我们就让$ x0 $ 移动到这个横坐标，然后开始下一次迭代，直到我们上一次迭代与下一次迭代的x的差距小于我们规定的值比如$ 1e-7 $，我们就认为迭代结束，然后返回结果

时间复杂度：O(log x)，此方法是二次收敛的，相较于二分查找更快。
空间复杂度：O(1)。

不保留小数

//牛顿迭代法,返回整数
func SqrtII(x int) int {

	c, x0 := float64(x), float64(x)

	for {
		//每次的切线方程都是y=2x0*x-x0^2
		xi := x0/2 + c/(2*x0)
		if math.Abs(xi-x0) < 1e-7 {
			break
		}
		x0 = xi
	}

	return int(x0)
}

保留小数

//牛顿迭代法保留4位小数
func SqrtToFloatII(x int) float64 {
	c, x0 := float64(x), float64(x)

	for {
		//每次的切线方程都是y=2x0*x-x0^2
		xi := x0/2 + c/(2*x0)
		if math.Abs(xi-x0) < 1e-7 {
			break
		}
		x0 = xi
	}
	fmt.Println(fmt.Sprintf("%.4f", x0))
	ret, _ := strconv.ParseFloat(fmt.Sprintf("%.4f", x0), 64)
	return ret
}