搜索算法4：插值搜索

介绍：

插值搜索是对二进制搜索的改进。这将有助于实现更好的时间复杂度。

说明：

正如我们在二分搜索中所看到的那样，我们始终采用中间索引，并根据该中间索引向左或向右移动。但是，如果我们有一个选择或公式来近似关键元素的位置怎么办？

这可以借助内插搜索来完成。
在插值搜索中，我们使用以下公式来获取靠近关键点的近似位置：

pos =低+（（键– arr[low]) * (high – low)) / (arr[high] – arr[low])

如果元素线性放置，则插补搜索将起作用。

让我们借助一个示例来理解：

考虑数组：
arr [] = {1,2,3,4,5,6,7,8};

搜索关键字= 7；

通过0：
最初，所有元素将具有以下值：

低= 0
高= 7
arr [low] = 1
arr [high] = 8

在上述值的帮助下，我们尝试使用上述公式找到最佳位置，将位置设为6。

AS arr [pos] = 7，这是搜索关键字，我们得到输出。

C ++解决方案

#include<iostream>
#include <vector>

using namespace std;

void interpolation_search( int arr[] , int len, int key) 
{
    int 低= 0;
    int high  = len -1;
    int pos;

    while (low < high)  
    {

        pos =低+（（键- arr[low]) * (high - low)) / (arr[high] - arr[low]);
        
        if (arr[pos] == key)
        {
            cout<<"The element is present"<<endl;
            return ;
        }
        if (key > arr[pos])
            low = pos + 1;
        else
            high = pos-1;
    }

    cout<<"The element is NOT present"<<cout<<endl;
    return ;
}

int main()
{
    int arr [] = {1,2,3,4,5,6,7,8};
    int len = 8;
    int key = 7;

    interpolation_search(arr, len, key);

    return 0;
}

输出：

The element is present

插值搜索将对排序后的数组元素起作用。
在最坏的情况下，该算法的时间复杂度将为O（log log N）。

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：