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.

advertisement

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
 
$ 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 Reference Books in C++ Programming, Data Structures and Algorithms.

advertisement

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn