Appearance
插值查找（Interpolation Search）
插值查找是二分查找的改进：不固定取中点，而是根据目标值与区间端点的比例关系，估算目标可能所在的位置。 当数据均匀分布时，插值查找期望 O(log log n) 次探针，远优于二分查找的 O(log n)。
查找过程
插值公式
设有序数组 A[lo..hi]，目标 target，插值探针位置按以下公式估算：
probe = lo + (target − A[lo]) / (A[hi] − A[lo]) × (hi − lo)
若 A[probe] = target，查找成功；若 A[probe] < target，在右半部分继续；否则在左半部分继续。这与二分查找的区别仅在于 probe 的计算方式：二分固定取 (lo+hi)/2，插值按"比例"动态估算。
过程模拟
以有序数组 [1, 3, 5, 7, 9, 11, 13]、目标 target = 11 为例：
算法特性
- 时间复杂度：均匀分布时期望 O(log log n)；最坏情况（极端非均匀分布）退化至 O(n)。
- 空间复杂度：O(1)，原地查找。
- 前提条件：必须是有序数组；数据分布越均匀，探针越精准。
- 与二分对比：均匀数据中插值往往一次命中；非均匀数据中二分更稳定。
| 算法 | 探针位置 | 均匀分布 | 非均匀分布 |
|---|---|---|---|
| 二分查找 | (lo+hi)/2，固定取中 | O(log n) | O(log n) |
| 插值查找 | 按比例估算，动态 | O(log log n) | 最坏 O(n) |
Baseline 任务：插值查找
任务内容
完成 ordered_search.cpp，实现以下函数：
- 插值查找
int InterpolationSearch(vector<int>& nums, int target)- 根据关键字分布估计查找位置，适用于分布较均匀的数据
- 返回目标所在下标，未找到返回 -1
- 注意
A[hi] == A[lo]时的边界处理（避免除以零）
文件结构
ordered_search.h：函数声明ordered_search.cpp：有序表查找核心实现test.cpp：测试程序，验证查找功能正确性
验证方式
- 编译：
g++ -std=c++17 test.cpp ordered_search.cpp -o testOrderedSearch - 运行：
./testOrderedSearch