习题- 二分法/牛顿迭代法 求算术平方根

一道编程题要用二分查找来求平方根，初学者表示黑人问号，这两个东西能放在一起使用吗？后来看了别人的实现，发现被二分查找的名字误导了，其实就是二分法

这个数是“找”出来的，也就是一个一个数的试，每次都计算 x^2 看等不等于 给定值。但是“找”这个过程，不应该是暴力测试所有区间内的数（也不可能完成），而是逐步缩小范围的，也就是二分法。二分法通过足够多的迭代，就可以得到有足够精度的解了。

这个方法同样可以用于求n次方根

下面是二分法实现（开平方）:

float my_sqrt_bin(float n) {
	float precision = 1e-4;
	float lo = 0.0;
	float hi = n;
	float mid = 0.0;
	float delta = 0.0;
	while (1)
	{
		mid = (lo + hi) / 2;
		delta = mid*mid - n;
		if (delta < -precision)lo = mid;
		else if (delta > precision)hi = mid;
		else return mid;
	}
}

注意：精度最好低于数据类型(float)最大精度一个数量级，否则会由于 (lo+hi)/2 一直等于 lo 而进入死循环

牛顿迭代法用来求解方程近似根，可以用于求解算数平方根，速度比二分法快不少（但受选定的初始点影响）࿱