关于数据结构:LeetCode069x的平方根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
  }
}