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  }}