查找算法之内插搜寻法

给定一个由n个均匀分布的值组成的排序数组arr[]，编写一个函数来搜索数组中特定的元素x。

线性搜索需要O(n)个时间，跳转搜索需要O(√n)个时间，二分搜索需要O(log n)个时间。

插值搜索是对实例的二进制搜索的改进，其中排序数组中的值是均匀分布的。插值在已知数据点的离散集范围内构造新的数据点。二分查找总是到中间的元素进行检查。另一方面，插值搜索可以根据被搜索键的值去不同的位置。例如，如果键的值更接近最后一个元素，插值搜索可能会从结束端开始搜索。

算法公式

为了找到要搜索的位置，使用以下公式。

//公式的思想是返回更高的pos值

//当要搜索的元素接近arr[hi]时。和

//当接近arr[lo]时更小的值

有许多不同的插值方法，其中一个被称为线性插值。线性插值取(x1,y1)和(x2,y2)两个数据点，公式为:在点(x,y)处。

这个算法的工作方式是我们在字典中搜索单词。插值搜索算法改进了二分搜索算法。求值的公式是 K = data-low/high-low.。

K是一个常数，用来缩小搜索空间。在二分搜索的情况下，这个常数的值是:K=(low+high)/2.

pos的公式可以推导如下。

假设数组的元素是线性分布的。

直线一般方程:y = m*x + c。

Y是数组中的值，x是它的下标。

现在把lo hi和x的值代入方程

arr[hi] = m*hi+c ----(1)

arr[lo] = m*lo+c ----(2)

x = m*pos + c ----(3)

m = (arr[hi] - arr[lo] )/ (hi - lo)

subtracting eqxn (2) from (3)

x - arr[lo] = m * (pos - lo)

lo + (x - arr[lo])/m = pos

pos = lo + (x - arr[lo]) *(hi - lo)/(arr[hi] - arr[lo])

算法

内插搜寻算法的其余部分除了上面的分区逻辑外是相同的。

步骤1:在循环中，使用上面给出的公式计算“pos”的值。

步骤2:如果匹配，返回该项的索引，并退出。

步骤3:如果项目小于arr[pos]，计算左子数组的探测位置。否则，在右子数组中进行相同的计算。

步骤4:重复操作，直到找到匹配项或子数组归零。

下面是算法的C代码递归方法实现。

// C program to implement interpolation search
// with recursion
#include <stdio.h>

// If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
int interpolationSearch(int arr[], int lo, int hi, int x)
{
    int pos;
    // Since array is sorted, an element present
    // in array must be in range defined by corner
    if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
        // Probing the position with keeping
        // uniform distribution in mind.
        pos = lo
            + (((double)(hi - lo) / (arr[hi] - arr[lo]))
                * (x - arr[lo]));

        // Condition of target found
        if (arr[pos] == x)
            return pos;

        // If x is larger, x is in right sub array
        if (arr[pos] < x)
            return interpolationSearch(arr, pos + 1, hi, x);

        // If x is smaller, x is in left sub array
        if (arr[pos] > x)
            return interpolationSearch(arr, lo, pos - 1, x);
    }
    return -1;
}

// Driver Code
int main()
{
    // Array of items on which search will
    // be conducted.
    int arr[] = { 10, 12, 13, 16, 18, 19, 20, 21,
                22, 23, 24, 33, 35, 42, 47 };
    int n = sizeof(arr) / sizeof(arr[0]);

    int x = 18; // Element to be searched
    int index = interpolationSearch(arr, 0, n - 1, x);

    // If element was found
    if (index != -1)
        printf("Element found at index %d", index);
    else
        printf("Element not found.");
    return 0;
}

输出

Element found at index 4

下面是算法的C++代码递归方法实现。

// C++ program to implement interpolation search by using iteration approach
#include<bits/stdc++.h>
using namespace std;

int interpolationSearch(int arr[], int n, int x)
{
    // Find indexes of two corners
    int low = 0, high = (n - 1);
    // Since array is sorted, an element present
    // in array must be in range defined by corner
    while (low <= high && x >= arr[low] && x <= arr[high])
    {
        if (low == high)
        {if (arr[low] == x) return low;
        return -1;
        }
        // Probing the position with keeping
        // uniform distribution in mind.
        int pos = low + (((double)(high - low) /
            (arr[high] - arr[low])) * (x - arr[low]));

        // Condition of target found
        if (arr[pos] == x)
            return pos;
        // If x is larger, x is in upper part
        if (arr[pos] < x)
            low = pos + 1;
        // If x is smaller, x is in the lower part
        else
            high = pos - 1;
    }
    return -1;
}

// Main function
int main()
{
    // Array of items on whighch search will
    // be conducted.
    int arr[] = {10, 12, 13, 16, 18, 19, 20, 21,
                22, 23, 24, 33, 35, 42, 47};
    int n = sizeof(arr)/sizeof(arr[0]);

    int x = 18; // Element to be searched
    int index = interpolationSearch(arr, n, x);

    // If element was found
    if (index != -1)
        cout << "Element found at index " << index;
    else
        cout << "Element not found.";
    return 0;
}
//this code contributed by Ajay Singh