Searching Algorithm 4: Interpolation Search

In this chapter we shall learn about below topics:

Interpolation search is an improvement to binary search. This will help to achieve better time complexity.

As we have seen in the binary search chapter, we always take the middle index and based on it, we shift towards left or right. But what if we have an option or a formula to approximate the position of the key element?

This can be done with the help of interpolation search.

In interpolation search we use below formula to get the approximate position that is near to the key:

Interpolation search will work if the elements are linearly placed.

Consider the array:

arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
and the search key = 7;

Initially all the elements will have below values:

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

With the help of above values we try to find an optimal position by using the above formula, we get the position as 6.

AS arr[pos] = 7, which is the search key, we get the output.

#include<iostream>
#include <vector>
 
using namespace std;
 
void interpolation_search( int arr[] , int len, int key) 
{
    int low = 0;
    int high  = len -1;
    int pos;
 
    while (low < high)  
    {
 
        pos = low + ((key - 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

Time complexity is O(log log N).