Interpolation search program in C++

In this chapter of C++ program tutorial out task is: 

• Write a C++ program to search an element using interpolation search in array
• Learn about time complexity of interpolation search

---

Interpolation search program in c++

Below is the C++ program to search an element using interpolation search.

/*  Program Author : Sayantan Bose
    Program Name : Interpolation Search
*/

#include<iostream>
using namespace std;

//Function for the interpolation search
void interpolationSearch(int arr[], int n, int key)
{
    int Low = 0, High = n-1;
    bool flag = true;
    //Checking the corner cases
    while(Low <= High && key >= arr[Low] && key <= arr[High])
    {
        if(Low == High)
        {
            cout<<"Element found at position "<<Low<<endl;
        }
        int q = (key - arr[Low])/(arr[High] - arr[Low]);
        int pos = Low + (High - Low) * q;
        if(arr[pos] == key)
        {
            cout<<"Element found at position "<<pos<<endl;
            flag = false;
        }
        //If the element is greater than the value at that position
        if(arr[pos] < key)
        {
            Low = pos + 1;
        }
        //If the element is lesser than the value at that position
        else
        {
            High = pos - 1;
        }
    }
    //If the element is not found after traversing the whole array
    if(flag == true)
    {
     cout<<"Element not found"<<endl;
    }
}

//Main function to take in the inputs from the user
int main()
{
    int n,i,x;
    cout<<"Enter the number of elements\n";
    cin>>n;
    int arr[n];
    cout<<"Enter the elements of the array\n";
    for(i=0;i<n;i++){
        cin>>arr[i];
    }
    cout<<"Enter the element to be searched\n";
    cin>>x;
    interpolationSearch(arr, n, x);
    return 0;
}

OUTPUT :

Enter the number of elements

Given below are required condition for interpolation search in c++ code:

• The array must be sorted in some order
• The elements must be uniformly distributed . By uniformly distributed it means that the element must be arranged in some particular order like in this example the elements are the square of the number.

EXPLANATION :

In the above interpolation search program in c++:

• The array is sorted and is in a particular sequence so use a formula to find the position of the element
• The formula used is  Low + (High - Low) ((key - Arr[Low]) /( Arr[High] - Arr[Low] ))  where Low is the first index of the array , High is the last index of the array and key is the element to be searched.
• If the elements are arranged in some sequence which has a common difference like 2 will give the position of the position of the element in one go.

COMPLEXITY ANALYSIS :

Given below are time complexity of interpolation search:

• Best time complexity = O(1)
• Average time complexity = O(log₂log₂n)
• Worst time complexity = O(n) (if elements are arranged in exponential order)
• Space complexity = O(1)

It might appear the binary search has a worst time complexity of O(logn) so what the use of interpolation search as it has a worst time complexity of O(n). The interpolation search is very beneficial when the elements are arranged in more sequencial way (for example, if we have a sorted array of elements whose elements have a common difference of 2 then in such case we can find the position of element in one go and it has a constant time complexity).

WORKING OF INTERPOLAION SEARCH PROGRAM :

 

You can see the above code execution and output in codeblocks IDE: