基于插值预测的快速查找算法

针对二分法的不足,提出了一种基于拉格朗日插值的动态预测查找算法,并将该算法和二分法结合得到改进的插值预测查找算法。改进算法在最坏的情况下,在含有n个元素的有序数列中,查找一个元素的最大循环比较次数为1到[log2n]+1之间,优于二分查找的[log2n]+1,最后从理论上证明了这一结论,并在求解一元高次方程实数解的应用中验证了这一结论。