PHP有序表查找之插值查找算法示例

一、概述

PHP有序表查找之插值查找算法是一种优化的二分查找算法，适用于数据分布较为均匀的数组。其原理是通过公式计算出待查找元素在有序表的位置估计值，从而可以缩小查找范围，提高查找效率。

二、算法思路

1. 计算待查找元素在有序表中的位置估计值，公式如下：

$$mid=low+\frac{(key-a[low])*(high-low)}{(a[high]-a[low])}$$

其中，$low$ 为当前查找区间的起始位置，$high$ 为结束位置，$key$ 为待查找的元素，$a$ 数组为有序表。

1. 通过估计值 $mid$ 可以得到一个缩小的查找范围，再进行二分搜索。如果查找成功，则返回该元素的位置，否则返回不存在的提示信息。

三、示例说明

以下是两种不同数据分布的示例。

1. 假设有一个长度为 $10$ 的有序数组 $a$，数据分布如下所示，查找元素为 $5$：

index	0	1	2	3	4	5	6	7	8	9
value	1	3	5	7	9	11	13	15	17	19

按照插值查找算法的公式，可以得到 $5$ 在有序数组中的位置估计值 $mid$ 为：

$$mid=0+\frac{(5-1)*(9-0)}{(19-1)}=2.84$$

即可缩小查找范围 $low=0$，$high=9$，$mid=2$。接着进行二分查找，发现 $a[mid]<key$，则在 $mid+1$ 到 $high$ 的区间内继续查找。最终找到了 $key=5$，返回 $2$。

1. 假设有一个长度为 $10$ 的有序数组 $a$，数据分布如下所示，查找元素为 $21$：

index	0	1	2	3	4	5	6	7	8	9
value	1	3	5	7	9	11	13	15	17	19

按照插值查找算法的公式，可以得到 $21$ 在有序数组中的位置估计值 $mid$ 为：

$$mid=0+\frac{(21-1)*(9-0)}{(19-1)}=9.37$$

即可缩小查找范围 $low=0$，$high=9$，$mid=9$。接着进行二分查找，发现 $a[mid]>key$，则在 $low$ 到 $mid-1$ 的区间内继续查找。最终没有找到 $key=21$，返回不存在的提示信息。