求解一个数的平方根在C/C++中是有库函数sqrt(n)的，那么除此之外我们自己实现有哪些方式呢？

下面介绍牛顿迭代法和二分搜索两种思想，其共同点都是不断逼近目标值，直至到最后可以得到最接近目标值的范围，从而得到目标值。

这里是参考的大佬博客：https://www.cnblogs.com/qlky/p/7735145.html

1.牛顿迭代法  

公式即Xi+1 = (xi + n / xi) * 1 / 2；

这里贴个代码：

#include<stdio.h>
#include<math.h>

const int N = 1e-5;
double To_sqrt(double a){
	double x2 = 1.0, x1;
	while(1){
		x1 = x2;
		x2 = 0.5 * (x1 + a / x1);
		
		if(fabs(x1 - x2) < 1e-5){
			return x2;
		}		
	}
	
}
int main()
{
	double a;
	
	scanf("%lf", &a);
	
	printf("%.3f\n", To_sqrt(a));
	
	return 0;
}

注意：其中初值x2是任取的，试将初值x2换为任意数均可得到如上结果。只是迭代的次数有差异.

 

2.二分搜索法

二分的思想就是我们可以得知平方根一定是在0~n/2+1之间的，不过这个限于整数的平方根。

二分条件就是如果x = left + right >> 1  的x^2 == n      return x;

如果x^2 < n那么就left = x; x^2 > n right = x;

退出条件为i > j 退出后返回return j;

具体还是见巨佬的博客吧：https://www.cnblogs.com/qlky/p/7735145.html