Articles

# 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(flag == true)
{
}
}

//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

7
Enter the elements of the array
1 4 9 16 25 36 49
Enter the element to be searched
16
Element found at position 3

REQUIRED CONDITION :

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(log2log2n)
• 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: CPP Programs

Would you like to see your article here on tutorialsinhand. Join Write4Us program by tutorialsinhand.com 