给出插值查找最差输入仍为线型

插值查找是基于二分查找的优化算法，它适用于有序的、均匀分布的数据集合。插值查找的核心思想是根据要查找的值在数据集合中的位置，计算出一个估计的位置，然后以该估计位置作为起点进行查找。因此，最差输入仍为线型。

考虑一个数据集合，它包含 n 个元素，且这些元素均匀分布在 [0, n-1] 这个区间内。如果要查找的值恰好是数据集合中的最后一个元素，那么插值查找的过程会一直向右移动，直到找到最后一个元素。因此，最坏情况下的比较次数为 n。由于这个数据集合是均匀分布的，因此可以认为这是线型的最坏情况。

举个例子，假设数据集合为 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]，要查找的值为 9。插值查找的过程如下：

1. 计算估计位置：

pos = low + (high - low) * (target - arr[low]) / (arr[high] - arr[low])

pos = 0 + (9 - 0) * (9 - 0) / (9 - 0) = 9

2. 由于估计位置 pos 大于 high，因此向右移动 low 和 high：

low = pos + 1 = 10

high = n - 1 = 9

3. 由于 low 大于 high，查找失败。

因此，在这种情况下，插值查找需要进行 n 次比较才能确定要查找的值是否存在于数据集合中。这也说明了插值查找的时间复杂度最坏情况下为 O(n)。