插值查找
入门比二分更"按值猜位置"，理解公式估计过程是关键。
// 搜索输入
定义数组和目标值
可视化演示开发中
插值查找 的交互式动画即将上线，敬请期待。
1int interpolationSearch(int arr[], int n, int target) {
2 int left = 0, right = n - 1;
3 while (left <= right && target >= arr[left] && target <= arr[right]) {
4 if (arr[left] == arr[right]) {
5 return arr[left] == target ? left : -1;
6 }
7 int pos = left + (target - arr[left]) * (right - left) / (arr[right] - arr[left]);
8 if (arr[pos] == target) return pos;
9 if (arr[pos] < target) left = pos + 1;
10 else right = pos - 1;
11 }
12 return -1;
13}
复杂度分析
时间 O(log log n)
空间 O(1)
最优 O(1)
最坏 O(n)
算法讲解
插值查找也要求数组升序，但它不固定检查中点，而是根据目标值在当前值域中的相对位置估算 probe 点。
如果数组分布比较均匀，probe 往往会直接落在离答案更近的位置，因此平均表现可能优于普通二分。
这也是为什么页面里会特别高亮左右边界和值域范围，因为公式正是基于这两个端点推算出来的。
当数据分布很不均匀时，公式猜测可能失准，算法性能也可能明显退化。
因此插值查找最适合"数值连续、分布接近均匀"的有序表，而不适合跨度极不稳定的数据。
平均时间复杂度常写作 O(log log n)，最坏情况下仍可能退化到 O(n)。