标签：二分
题目：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 }}