LeetCode069-x的平方根-easy

标签:二分
题目:x的平方根
题号:69
题干:实现 int sqrt(int x) 函数。计算并返回 x 的平方根,其中 x 是非负整数。由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去

示例1:
输入: 4
输出: 2

示例2:
输入: 8
输出: 2
解释: 8的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去

原题比较简单,因此这里做简单的变形,求x的平方根,要求可以获取指定精度的结果

示例:
输入:8 0.000001
输出:2.828427
说明:0.000001表示精确到小数点后六位

思路:

• 要求x的平方根,最容易想到的就是从1到x,一个一个的试,这种方法的时间复杂度是O(n),这不是我们想要的
• 二分查找算法,显然是用来查找的算法,我们的目的也算是查找。如果你看过我的上一篇二分查找的文章,里边有说到什么情况下会想到用二分查找,比如我们要查找的一系列数是有序的等,我们要求x的平方根,那肯定在[1, x]这个区间找(x>1),它显然是有序的。这自然 会想到用二分来查找
• 使用二分查找算法,需要两个游标low和high。需要考虑他们的初始值是什么?以及当mid不满足时,low和hight如何变化?
• 既然是求x的平方根,x的值有两种情况。第一种是x<1,这种情况,我们要求的结果肯定在[0, 1]这区间内,所以就可以初始化low = 0,hight=1,那mid就为(low+hight)/2
• x的第二种情况就很简单了,当x>1时,它的平方根的值肯定在[1, n]区间内,所以low = 1, high=x,mid = (low+hight)/2
• 不难想到,当x-mid*mid < 0时,说明mid太大,那此时我们就应该在[1, mid]之间找,即,此时让hight=mid-1
• 如果x-midmid > 0,这时要考虑x-midmid是否大于我们要求的精度,如果大于这个精度,那此时low = mid+1
• 有了以上这些条件,基本上这道题就出来了。如果你按照上边的思路把代码写出来之后会发现是有问题的,当x<1的时候程序就不能正常运行了。原因是low和high变化的时候,如果x<1的时候,结果肯定是小于1的,如果直接让high或low为mid加1或减1肯定就不对了
• 因此,当x-mid*mid < 0时,应该让high=(mid+high)/2

代码实现

func SolutionSqrt(num float64, precision float64) float64 {
 if num < 0 {
 fmt.Println("参数不合法")
 return -1.000
 }
 var low,high float64
 if num > 1 {
 low = 1
 high = num
 } else {
 low = num
 high = 1
 }
 return Sqrt(num, low, high, precision)
}
func Sqrt(num float64, low float64, high float64, precision float64) float64 {
 mid := (low+high) / 2
 if num - (mid * mid) < 0 {
 return Sqrt(num, low, (mid+high)/2, precision)
 } else {
 if num - (mid * mid) > precision {
 return Sqrt(num, (low + mid)/2, high, precision)
 }
 return mid
 }
}

本文来自:Segmentfault

感谢作者:书旅

查看原文:LeetCode069-x的平方根-easy

• 编辑
• 预览