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

Fast Search Algorithm Based on Interpolation Prediction

作　　者：叶三星[1] 高伟[1] 古富强[1] 李维良[1] 

机构地区：[1]中国地质大学(武汉)信息工程学院

出　　处：《软件导刊》2011年第11期63-65,共3页Software Guide

基　　金：国家自然科学基金项目(41002115)

摘　　要：针对二分法的不足,提出了一种基于拉格朗日插值的动态预测查找算法,并将该算法和二分法结合得到改进的插值预测查找算法。改进算法在最坏的情况下,在含有n个元素的有序数列中,查找一个元素的最大循环比较次数为1到[log2n]+1之间,优于二分查找的[log2n]+1,最后从理论上证明了这一结论,并在求解一元高次方程实数解的应用中验证了这一结论。The binary search algorithm is not enough good,so this paper presented dynamic prediction search algorithm based on Lagrange interpolation,and it combined the algorithm and binary search algorithm and presented an improved interpolation prediction algorithm based on them.In the worst case,it compared times to find an element of an array by using the improved algorithm,and it was proved to be obviously better than binary search algorithm in theory,and at last this conclusion was verified in the application of solving the real number solutions of higher degree equation.

关 键 词：拉格朗日插值 动态预测 改进算法 一元高次方程实数解 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]