数据结构与算法面试总结

如何使用加减乘除求出一个实数的平方根（立方根）？大体上有两种思路：二分查找法和牛顿迭代法。

二分查找法

这种方法的主要思想是：先确定解的范围，然后在此范围内不断的做二分查找，直到满足精度要求。

设输入的实数为$a$，此处假定$a$为正数

• $a\geq 1$时，$\sqrt{a}$ 满足 $1\leq \sqrt{a}\leq a$
• $0\leq a\leq 1$时，$\sqrt{a}$则满足$a\leq \sqrt{a}\leq 1$ 注意到两种情况的区间是相反的。接下来只需要在这个区间进行二分查找即可。

牛顿迭代法

这种方法的思想是：将此问题作为求解方程的根的问题，然后使用数值计算的方法求解。

具体说来，设输入实数为$a$，目标是求$x = \sqrt{a}$，因此求解其中的$x$也就是求解方程$x^2-a=0$的根。此方程是一个非线性方程。

非线性方程的数值求解方法有多种，上面的二分法就是一种简单的方法，而牛顿迭代法则是一个更为快速有效的求解方法。

关于牛顿法的介绍可以参见此链接。

可以证明，对于常见的函数，牛顿迭代法一定收敛