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 = n1;
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
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(log_{2}log_{2}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:
Would you like to see your article here on tutorialsinhand.
Join
Write4Us program by tutorialsinhand.com
About the Author
Sayantan Bose
 š Iām currently working on DS Algo skills
 š± Iām currently learning web develeopement
 šÆ Iām looking to collaborate with Oppia
 š« Reach me at https://www.linkedin.com/in/sayantanbose14134a1a6/
 š Pronouns: his/him
Page Views :
Published Date :
Dec 20,2020