#|《力扣刷题》二分查找（x 的平方根）力扣|二分查找|算术平方根|二

题目描述若存在一个非负整数 x，计算并返回 x 的算术平方根
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去
C 语言具体代码实现二分查找的具体过程如下！！！

#include int mySqrt(int x){ long left = 1, right = x; // 设置左右边界 while(left <= right){ long mid = (left+right)/2; long square = mid * mid; if(square > x){ right = mid - 1; }else if(square < x){ left = mid + 1; }else{ return mid; } } return right; } int main() { int num1 = mySqrt(4); int num2 = mySqrt(8); int num3 = mySqrt(11); printf("%d %d %d", num1, num2, num3); // 2 2 3 return 0; }

另外此题还有另一种解法：牛顿迭代！！！
牛顿迭代是一种可以用来快速求解函数零点的方法
若我们用 C 表示待求出平方根的那个整数，那么 C 的平方根就是函数

文章图片
的零点
牛顿迭代法的本质是借助泰勒级数，从初始值开始快速向零点逼近；我们任取一个

文章图片
作为初始值，在每一步的迭代中，我们找到函数图像上的点

文章图片
，过该点作斜率

文章图片
的直线，与横轴的交点记为

文章图片
（请自己求交点），

文章图片
相较于

文章图片
距离零点更近，在经过多次迭代后，我们就可以得到一个距离零点非常接近的交点，下图给出了从?

文章图片
开始迭代两次，得到

文章图片
和

文章图片
的过程

文章图片

#include #include int mySqrt(int x){ if(x == 0){ return 0; } double C = x, x0 = x; while(true){ double xi = 0.5*(x0 + C/x0); if((x0 - xi) < 1e-7){ break; } x0 = xi; } return (int)x0; } int main() { int num1 = mySqrt(4); int num2 = mySqrt(8); int num3 = mySqrt(11); printf("%d %d %d", num1, num2, num3); // 2 2 3 return 0; }

【#|《力扣刷题》二分查找（x 的平方根）】