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.

//This is a C++  Program to implement Interpolation Search Algorithm.

```
#include <iostream>
```
```
using namespace std;
```
```
 
```
```
//Print array values
```
```
void print_ar (int ar[], int size)
```
```
{
```
```
  for (int i = 0; i < size; ++i)
```
```
  {
```
```
    cout << ar[i] << " ";
```
```
  }
```
```
    cout << endl;
```
```
}
```
```
 
```
```
//Interpolation Search
```

int interpolation_search (int ar[], int value, int size)

```
{
```
```
  int low = 0;
```
```
  int high = size - 1;
```
```
  int mid;
```
```
 
```

  while (ar[low] <= value && ar[high] >= value)

```
  {
```

    mid = low + ((value - ar[low]) * (high - low)) / (ar[high] - ar[low]);

```
    if (ar[mid] < value)
```
```
    {
```
```
      low = mid + 1;
```
```
    }
```
```
    else if (ar[mid] > value)
```
```
    {
```
```
      low = mid - 1;
```
```
    }
```
```
    else
```
```
    {
```
```
      return mid;
```
```
    }
```
```
  }
```
```
 
```
```
  if (ar[low] == value)
```
```
  {
```
```
    return low;
```
```
  }
```
```
  else
```
```
  {
```
```
    return -1;
```
```
  }
```
```
}
```
```
 
```
```
//Driver Function
```
```
int main()
```
```
{
```

  int ar [] = {1, 2, 78, 18, 16, 30, 29, 2, 0, 199};

```
  int value, pos;
```
```
 
```
```
  cout << "Your Array : ";
```
```
  print_ar (ar, 10);
```
```
 
```

  cout << "Enter the value to search : ";

```
  cin >> value;
```

  pos = interpolation_search (ar, value, 10);

```
  if (pos != -1)
```
```
  {
```

    cout << "Value Found! at position : " << pos + 1 << endl;

```
  }
```
```
  else
```
```
  {
```

    cout << "Sorry, the value you searched for is not present." << endl;

```
  }
```
```
 
```
```
  return 0;
```
```
}
```

Output :

 
$ 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.

Subscribe Now: C++ Algorithms Newsletter | Important Subjects Newsletters

« Prev - C++ Program to Implement Bucket Sort

» Next - C++ Program to Find the Shortest Path using Bellman Ford Algorithm

Related Posts:

Recommended Articles: