Interpolation Search Algorithm In C++

In this tutorial, we will learn how to implement Interpolation Search in C++ with the algorithm.

What is Interpolation Search?

You must be knowing several searching algorithms. In this tutorial, we are going to discuss about Interpolation Search in C++. We apply this Interpolation Search Algorithm into an array which is sorted. It is an improvement over Binary Search. Interpolation search may go to different locations according to the value of the key we are searching. For example, if the value of the key is near to the last element, Interpolation Search Algorithm is likely to start search toward the end side.

To find the position that we have to search, it uses the following formula:

pos = st + [ (x – array[st])*(end – st) / (array[end] – array[st]) ]

array[] : Array where elements need to be searched
x : Element to be searched
st : Starting index in array[]
end : Ending index in array[]

C++ program for interpolation search implementation




#include<bits/stdc++.h> 
using namespace std; 
   
int interpolation_search(int array[], int num, int x) 
{ 
    // Find indexes of two corners 
    int st = 0, end = (num - 1); 
  
    while (st <= end && x >= array[st] && x <= array[end]) 
    { 
        if (st == end) 
        { 
            if (array[st] == x) return st; 
            return -1; 
        } 
        
        int pos = st + (((double)(end - st) / 
            (array[end] - array[st])) * (x - array[st]); 
  
        if (array[pos] == x) 
            return pos; 
  
        // If x is larger, x is in upper part 
        if (array[pos] < x) 
            st = pos + 1; 
  
        // If x is smaller, x is in the lower part 
        else
            end = pos - 1; 
    } 
    return -1; 
} 
  
// Driver Code 
int main() 
{ 
     
    int array[] = {10, 12, 13, 16, 18, 19, 20, 21, 
                 22, 23, 24, 33, 35, 42, 47}; 
    int num = sizeof(array)/sizeof(array[0]); 
  
    int x = 18; //This is the element you want to search 
    int index = interpolation_search(arr, n, x); 
  
    // If element was found 
    if (index != -1) 
        cout << "Element found at index " << index; 
    else
        cout << "Element not found."; 
    return 0; 
} 
Output:
Element found at index 4

If there is uniform distribution among elements, then interpolation search algorithm’s complexity can be upto O (log log n)). In the worst case, it can take upto O(n).

Explanation of my code:

  1. I have created a function which may seem complex looking at first but it is very simple.
  2. I have passed an array, num and x as arguments in the function.
  3. Here array is the given array of elements, num is the size of array and x is value to search.
  4. Now let’s talk about inside of the function. Starting index is equal to 0 and ending index is equal to size -1.
  5. Now if there is only one element in array i.e st=end, and the present element is x, we will return the index else goto 5.
  6. If 4 is not fulfilled, we will search by using the formula given above.
  7. If the element is at the index computed using the formula pos, return the index position pos else goto 7.
  8. Make the starting index  pos+1, if element at pos is less than else goto 9.
  9. Make the ending position as pos-1, if element at pos is greater than x.
  10. Next, there is main() program to test the given code.

Prerequisite is a Binary search.

For any queries, post your doubts in comments.


Leave a Reply

Your email address will not be published. Required fields are marked *