Articles

Interpolation search program in C++

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

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 :

working of interpolation search

 

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

cpp program to find an element using interpolation search output

 


CPP Programs

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/sayantan-bose-14134a1a6/ - šŸ˜„ Pronouns: his/him
Page Views :    Published Date : Dec 20,2020  
Please Share this page

Related Articles

Like every other website we use cookies. By using our site you acknowledge that you have read and understand our Cookie Policy, Privacy Policy, and our Terms of Service. Learn more Got it!