插值查找是PHP中针对有序数组优化的查找算法，它在二分查找的基础上，利用目标值与数组首尾元素的数值关系，预估目标值的大致位置，从而减少不必要的比较次数，在数值分布均匀的有序数组中效率表现更优。
插值查找的核心原理
二分查找每次都从数组中间位置开始比较，而插值查找通过下面的公式预估目标值的位置：
mid = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left])
其中left是数组左边界索引，right是右边界索引，target是要查找的目标值，arr是有序数组。这个公式会根据目标值在数组数值范围内的相对位置，动态调整查找的起始点，避免固定从中间开始查找的局限性。
PHP实现插值查找的代码示例
下面是一个完整的PHP插值查找实现，支持在升序有序数组中查找目标值，返回目标值的索引，未找到则返回-1：
<?php
/**
* PHP插值查找函数
* @param array $arr 升序有序数组
* @param int $target 要查找的目标值
* @return int 目标值索引，未找到返回-1
*/
function interpolationSearch($arr, $target) {
$left = 0;
$right = count($arr) - 1;
// 数组为空或目标值不在数组数值范围内时直接返回-1
if ($right < 0 || $target < $arr[$left] || $target > $arr[$right]) {
return -1;
}
while ($left <= $right) {
// 计算预估中间位置，避免除数为0的情况
if ($arr[$right] == $arr[$left]) {
// 数组所有元素相同的情况，直接判断左边界是否等于目标值
return $arr[$left] == $target ? $left : -1;
}
$mid = $left + (int)(($right - $left) * ($target - $arr[$left]) / ($arr[$right] - $arr[$left]));
// 确保mid在合法索引范围内
if ($mid < $left || $mid > $right) {
return -1;
}
if ($arr[$mid] == $target) {
return $mid;
} elseif ($arr[$mid] < $target) {
$left = $mid + 1;
} else {
$right = $mid - 1;
}
}
return -1;
}
// 测试示例
$sortedArr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
$target1 = 13;
$target2 = 8;
$result1 = interpolationSearch($sortedArr, $target1);
$result2 = interpolationSearch($sortedArr, $target2);
echo "查找{$target1}的结果：" . ($result1 != -1 ? "找到，索引为{$result1}" : "未找到") . PHP_EOL;
echo "查找{$target2}的结果：" . ($result2 != -1 ? "找到，索引为{$result2}" : "未找到") . PHP_EOL;
?>
插值查找的使用注意事项
- 插值查找仅适用于数值型有序数组，且数组元素分布尽量均匀，否则预估位置的准确性会下降，效率可能不如二分查找。
- 使用前需要确认数组是升序排列的，如果是降序数组需要调整比较逻辑。
- 当数组中存在大量重复元素时，需要额外处理重复值的查找逻辑，上述示例仅返回第一个匹配到的索引。
- 计算mid时需要注意整数溢出的问题，PHP中整数范围较大，常规场景下不需要额外处理，但如果数组长度极大可以做类型转换。
插值查找与二分查找的差异
| 对比项 | 插值查找 | 二分查找 |
|---|---|---|
| 位置计算方式 | 根据目标值预估位置 | 固定取中间位置 |
| 适用场景 | 数值分布均匀的有序数组 | 所有有序数组 |
| 平均时间复杂度 | O(log log n)（分布均匀时） | O(log n) |
| 最坏时间复杂度 | O(n)（分布极不均匀时） | O(log n) |
实际应用场景
插值查找适合用在需要频繁查找、数组数值分布规律的场景，比如根据年龄查找用户列表、根据价格区间查找商品列表、根据分数段查找成绩记录等。如果数组数值分布非常不均匀，建议优先选择二分查找保证稳定的查找效率。