插值搜索

Harshit Jindal 2023年1月30日 2021年2月28日
  1. 插值搜索算法
  2. 插值搜索示例
  3. 插值搜索算法的实现
  4. 插值搜索算法的复杂度
插值搜索

插值搜索是一种快速高效的搜索算法。它改进了二叉搜索算法,适用于数组元素均匀分布在排序数组上的场景。它的工作原理是探测所需值的位置。与二叉搜索不同的是,它并不总是去数组的中间,而是可能根据要搜索的键值去任何位置。我们比较估计位置的值,并将搜索空间缩小到它之后或之前的部分。例如,当我们在字典中搜索一个单词时,我们根据里面字母的位置来翻页,而不是每次都把搜索空间分成两半。

插值搜索算法

假设我们有一个未排序的数组 A[],包含 n 个元素,我们想找到一个给定的元素 X

  • lo0mid-1hin-1
  • lo<=hi,且 X 位于 lo 和 hi 之间的范围时,即 X >= A[lo]X <= A[hi]
    • 利用探测位置的公式计算 mid - mid = lo + (X - A[lo]) * (hi - lo) / (A[hi] - A[lo])
    • 如果探测位置的元素小于目标元素,则向右移动。如果 A[mid]<X,则设置 lomid + 1
    • 否则,如果元素大于目标元素,则向左移动。如果 A[mid]>X,则设置 himid-1
    • 否则我们已经找到了元素并返回 mid
  • 如果 lo=hi,只剩下一个元素,检查它是否是目标元素,即如果 A[lo]==X
    • 如果 true,则返回 lo
    • 否则返回 -1

插值搜索示例

假设我们有一个数组 - (1, 3, 7, 8, 11, 15, 17, 18, 21),我们想找到 X - 18

  • lo=0mid=-1hi=8
  • 利用公式-0+(18-1)*(8-0)/(21-1) 计算 mid6
  • 然后我们将 A[6]X 进行比较,看其较小,设 lo7
  • 7+(18-18)*(8-7)/(21-18) 计算 mid
  • 然后我们将 A[7]X 进行比较,看是否等于 18,并返回指数 7

插值搜索算法的实现

#include <bits/stdc++.h>
using namespace std;

int interpolation_search(int arr[], int n, int X)
{
    int lo = 0;
    int hi = n - 1;
    int mid;

    while ((arr[hi] != arr[lo]) && (X >= arr[lo]) && (X <= arr[hi])) {
        mid = lo + ((X - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));

        if (arr[mid] < X)
            lo = mid + 1;
        else if (X < arr[mid])
            hi = mid - 1;
        else
            return mid;
    }

    if (X == arr[lo])
        return lo ;
    else
        return -1;
}

int main(void)
{
    int n = 9;
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int x = 4;
    int result = interpolation_search(arr, n, x);
    if (result == -1) {
        cout << "Element not found !!";
    }
    else cout << "Element found at index " << result;
    return 0;
}

插值搜索算法的复杂度

时间复杂度

  • 平均情况

该算法的平均时间复杂度为 O(log(logn))。当数组内的所有元素都均匀分布时,就会出现这种情况。

  • 最佳情况

当我们要搜索的元素是插值搜索所探查的第一个元素时,就会出现最佳情况。最佳情况下算法的时间复杂度是 O(1)

  • 最坏情况

最坏的情况发生在目标的数值成倍增加的时候。最坏情况下算法的时间复杂度为 O(n)

空间复杂度

这种算法的空间复杂度是 O(1),因为除了临时变量外,它不需要任何数据结构。

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相关文章 - Search Algorithm