C++ Program to Implement Interpolation Search Algorithm

This C++ Program implements Interpolation Search Algorithm.

Interpolation search is a search algorithm for a given key value in an indexed array that has been ordered by the values of the key. It is also referred as extrapolation search.

It is based on how humans search through a telephone book for a particular name.

Average case time complexity of interpolation search is O(logn(logn)) comparisons, where n is the number of the elements to be searched. In worst case it can make up to O(n) comparison which is equivalent to linear search.

The program has an input array of size 10 initialized with 10 values. This returns index of the element, if found and -1 if not using Interpolation Search Algorithm.
Here is source code of the C++ Program to Implement Interpolation Search Algorithm. The C++ program is successfully compiled and run on g++-4.3.2 on a Linux system. The program output is also shown below.

  1. //This is a C++  Program to implement Interpolation Search Algorithm.
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. //Print array values
  6. void print_ar (int ar[], int size)
  7. {
  8.   for (int i = 0; i < size; ++i)
  9.   {
  10.     cout << ar[i] << " ";
  11.   }
  12.     cout << endl;
  13. }
  14.  
  15. //Interpolation Search
  16. int interpolation_search (int ar[], int value, int size)
  17. {
  18.   int low = 0;
  19.   int high = size - 1;
  20.   int mid;
  21.  
  22.   while (ar[low] <= value && ar[high] >= value)
  23.   {
  24.     mid = low + ((value - ar[low]) * (high - low)) / (ar[high] - ar[low]);
  25.     if (ar[mid] < value)
  26.     {
  27.       low = mid + 1;
  28.     }
  29.     else if (ar[mid] > value)
  30.     {
  31.       low = mid - 1;
  32.     }
  33.     else
  34.     {
  35.       return mid;
  36.     }
  37.   }
  38.  
  39.   if (ar[low] == value)
  40.   {
  41.     return low;
  42.   }
  43.   else
  44.   {
  45.     return -1;
  46.   }
  47. }
  48.  
  49. //Driver Function
  50. int main()
  51. {
  52.   int ar [] = {1, 2, 78, 18, 16, 30, 29, 2, 0, 199};
  53.   int value, pos;
  54.  
  55.   cout << "Your Array : ";
  56.   print_ar (ar, 10);
  57.  
  58.   cout << "Enter the value to search : ";
  59.   cin >> value;
  60.   pos = interpolation_search (ar, value, 10);
  61.   if (pos != -1)
  62.   {
  63.     cout << "Value Found! at position : " << pos + 1 << endl;
  64.   }
  65.   else
  66.   {
  67.     cout << "Sorry, the value you searched for is not present." << endl;
  68.   }
  69.  
  70.   return 0;
  71. }

Output :

advertisement
advertisement
 
$ g++ InterpolationSearch.cpp
$ ./a.out
 
Your Array : 1 2 78 18 16 30 29 2 0 199 
Enter the value to search : 2
Value Found! at position : 2
 
Your Array : 1 2 78 18 16 30 29 2 0 199 
Enter the value to search : 4
Sorry, the value you searched for is not present.

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.