编辑“︁插值搜索”︁

{{DISPLAYTITLE:插值搜索}}

'''插值搜索'''（Interpolation Search）是一种改进的[[二分搜索]]算法，适用于'''均匀分布的有序数组'''。它通过计算目标值的预估位置来减少比较次数，平均时间复杂度为<math>O(\log \log n)</math>，但在最坏情况下（如非均匀分布数据）会退化为<math>O(n)</math>。

== 算法原理 ==
插值搜索基于以下假设：如果数组元素均匀分布，则目标值的位置可通过线性插值公式估算：
<math>
pos = low + \left\lfloor \frac{(x - arr[low]) \times (high - low)}{arr[high] - arr[low]} \right\rfloor
</math>
其中：
* <code>arr</code> 是已排序数组
* <code>x</code> 是目标值
* <code>low</code> 和 <code>high</code> 是当前搜索区间的边界

=== 与二分搜索对比 ===
{| class="wikitable"
|+ 插值搜索 vs 二分搜索
! 特性 !! 插值搜索 !! 二分搜索
|-
| 时间复杂度（平均） || <math>O(\log \log n)</math> || <math>O(\log n)</math>
|-
| 数据要求 || 必须均匀分布 || 任意有序数据
|-
| 分区方式 || 动态计算位置 || 固定中点
|}

== 算法步骤 ==
1. 计算目标值的预估位置 <code>pos</code>
2. 若 <code>arr[pos] == x</code>，返回位置
3. 若 <code>arr[pos] < x</code>，在右子数组（<code>pos+1</code> 到 <code>high</code>）继续搜索
4. 若 <code>arr[pos] > x</code>，在左子数组（<code>low</code> 到 <code>pos-1</code>）继续搜索
5. 重复直到找到目标或区间无效

== 代码实现 ==
以下是Python实现示例：

<syntaxhighlight lang="python">
def interpolation_search(arr, x):
    low = 0
    high = len(arr) - 1
    
    while low <= high and arr[low] <= x <= arr[high]:
        # 计算插值位置
        pos = low + ((x - arr[low]) * (high - low)) // (arr[high] - arr[low])
        
        if arr[pos] == x:
            return pos
        elif arr[pos] < x:
            low = pos + 1
        else:
            high = pos - 1
    
    return -1  # 未找到
</syntaxhighlight>

=== 示例输入输出 ===
输入：
<syntaxhighlight lang="python">
arr = [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47]
x = 18
</syntaxhighlight>

执行过程：
1. 初始 <code>low=0</code>, <code>high=14</code>
2. 计算 <code>pos = 0 + ((18-10)*(14-0))//(47-10) ≈ 4</code>
3. <code>arr[4] = 18</code> 匹配，返回索引4

输出：
<pre>
Found at index 4
</pre>

== 复杂度分析 ==
* '''最佳情况'''：<math>O(1)</math>（第一次命中）
* '''平均情况'''：<math>O(\log \log n)</math>（均匀分布数据）
* '''最坏情况'''：<math>O(n)</math>（如 <code>[1,2,3,4,5,10000]</code> 搜索5）

<mermaid>
graph LR
    A[开始] --> B{计算pos}
    B -->|命中| C[返回索引]
    B -->|小于| D[搜索右子数组]
    B -->|大于| E[搜索左子数组]
    C --> F[结束]
    D --> B
    E --> B
</mermaid>

== 应用场景 ==
1. '''电话簿搜索'''：人名按字母均匀分布时效率极高
2. '''大规模科学数据'''：如温度传感器记录的均匀时间序列
3. '''游戏高分榜'''：分数分布均匀的排名系统

== 注意事项 ==
* 必须确保数组已排序且'''分布均匀'''，否则性能可能劣于二分搜索
* 对于小规模数据集（<100元素），线性搜索可能更简单高效
* 浮点数数组需处理除零错误（当<code>arr[high]==arr[low]</code>时）

== 扩展优化 ==
可结合'''指数搜索'''（Exponential Search）先确定大致范围，再使用插值搜索精确定位，尤其适合未知大小的有序数据集。

[[Category:搜索算法]]
[[Category:数据结构与算法]]
[[Category:计算机科学]]