本文描述了PHP有序表搜索的插值搜索算法。分享给大家参考，如下：

前言：

我们之前介绍过二分搜索法，但是让我们考虑一下。为什么我们要把它分成两半？而不是四分之一或更多？

比如你在英文字典里找“苹果”，打开字典的时候是下意识的翻首页还是封底？如果你再查一次“动物园”，你会怎么查？显然，你不会从字典的中间开始，而是带着某种目的向前或向后转。

类似的，比如在0 ~ 10000范围内由小到大均匀分布100个元素的数组中找5，我们自然会先考虑数组的较小的索引。

上面的分析其实就是插值搜索的思想，是二分搜索法的一个改进。

基本思想：

基于待搜索关键字关键字与查找表中最大和最小记录的关键字进行比较的搜索方法的核心在于插值计算公式。我们先来看看二分搜索法的计算公式：

插值搜索是对其中的1/2进行改进，变成如下的计算方案：

插值搜索算法的核心在于插值：的计算公式

$ num-$ arr[$较低]——3354——3354——3354——-$ arr[$较高]-$ arr[$较低]

代码：

？Php//插值搜索(前提是数组必须是有序的)事件复杂度O(logn)//但是由于数组长度比较大，关键字分布比较均匀，插值搜索的效率要高于二分搜索法$ I=0；//存储比较的次数//@要搜索的param Array//@要搜索的param Number Function insertSearch($ arr，$ num){ $ count=count($ arr)；$ lower=0；$ high=$ count-1；全球$ I；而($ low=$ high){ $ I；//counter if($ arr[$ lower]==$ num){ return $ lower；} if($ arr[$ high]==$ num){ return $ high；}//搜索减半：$ middle=int val(($ low $ high)/2)；$ middle=intval($ low($ num-$ arr[$ low])/($ arr[$ high]-$ arr[$ low])*($ high-$ low))；if($ num $ arr[$ middle]){ $ high=$ middle-1；} else if($ num $ arr[$ middle]){ $ lower=$ middle 1；} else { return $ middle} } return-1；}$arr=array(0，1，16，24，35，47，59，62，73，88，99)；$pos=insertsearch($arr，62)；打印($ pos)；echo“br”；echo $ I；总结：

在时间复杂度方面，也是O(logn)，但是对于长有序表和均匀的关键词分布，插值搜索算法的平均性能要比二分搜索法好得多。相反，如果数组中的分布类似于{0，1，2，2000，2001，99998，999999}，这样极不均衡的数据，用插值搜索可能不是很合适的选择。

我自己做了一个特别的例子：

$arr=array(0，1，2，2000，2001，2002，2003，2004，5555，69666，99999，100000)；回声“位置：”。binsearch(5555美元)；echo“br”；Echo的比较次数：“”。$ I；$ I=0；//重置比较时间回声“br”；回声“位置：”。insert search(arr，5555美元)；echo“br”；Echo的比较次数：“”。$ I；结果输出：

位置：8比较次数：2位置：8比较次数：9。对于极不均匀的数据，插值搜索效率低于二分搜索法。

PS:上面提到的binsearch()函数可以参考前面的PHP有序表搜索——二分搜索法(一半)

更多对PHP相关内容感兴趣的读者可以查看本网站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》、《PHP数学运算技巧总结》、0103010

希望本文对PHP编程有所帮助。