C 语言插值查找

在本文中，我们将讨论 C 语言中的插值搜索及其情况、示例和输出。

当排序数组中的值均匀分布时，插值搜索比二分搜索更受欢迎。对已知数据点的离散集进行插值以创建落在其范围内的新数据点。二分搜索总是检查中间元素。另一方面，插值搜索的位置将由所搜索键的值决定。例如，如果键值更接近最后一个元素，插值搜索可能会从末尾开始搜索。

如果数组中存在一个元素，我们必须编写一个 C 程序，使用插值搜索算法来确定其在整数数组中的位置。

插值搜索的几种情况

插值搜索有几种情况。这些情况如下：

1. 平均情况

插值搜索通常执行 (log(log n)) 次比较，其中 n 是元素的总数。

示例

如果输入数组包含以下数据：1, 2, 3, 4, 5, 6，并且要搜索的元素是元素 6，则预期结果将是位置 6。

平均情况下的时间复杂度是 O(log(log n))。

2. 最佳情况

如果所寻找的对象是数组的中间元素，插值搜索只进行一次比较并返回位置。

示例

如果输入数组包含数据 “2, 4, 6, 8, 10,”，并且要搜索的元素是 “6”，则预期输出将是位置 3。最佳情况下的时间复杂度是 O(1)。

示例代码

这是使用整数数组实现插值搜索的 C 程序代码。使用 GCC 编译器，该程序已成功编译和测试。下面还给出了程序的输出。

争议解决

1. 插值搜索是对二分搜索的改进。数据必须经过排序且均匀分布才能使用插值搜索。
2. 插值搜索使用公式 “mid = bottom + (top - bottom) * ((item - a[bottom]) / (a[top] - a[bottom]))” 来确定数组的中间位置。
3. 标准插值搜索的平均情况时间复杂度为 O(log(log n))，这表明它比二分搜索和线性搜索快得多。

代码

输出

测试用例 1

Enter total elements (num < 200) :5
Enter 5 Elements in ascending order:
1
2
3
4
5
Search For : 4
Element 4 found at position 4

测试用例 2

Enter total elements (num < 200) :6
Enter 5 Elements in ascending order:
1
2
3
4
5
6
Search For: 2
Element 2 found at position 2

程序说明

1. 在进行插值搜索之前，数据必须经过排序且均匀分布。我们要么将数组按升序排序，要么必须将元素按升序插入到数组中。
2. 如果我们要进行插值搜索，我们使用中间公式将数组分成几个部分，并确定所寻找的键值是否存在于任何被分割的部分中。
3. 该算法通过比较公式确定的数组的中间值与被搜索的键值来选择搜索区域。
4. 这个过程持续进行，函数定义内部数组的顶部和底部，或者起始索引和结束索引不断移动，直到我们找到该元素。
5. 插值搜索的关键在于它只能与均匀分散和排序的数组一起使用。