Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values).By comparison, binary search always chooses the center of the remaining search space, discarding one half or the other, depending on the comparison between the key found at the estimated position and the key seek — it makes not necessitate numerical values for the keys, exactly a total order on them.

It can be useful for locating a record in a large sorted file on disk, where each probe necessitates a disk seek and is much slower than the interpolation arithmetical. index structures like B-trees also reduce the number of disk accesses, and are more often used to index on-disk data in part because they can index many types of data and can be updated online.

```
#include <iostream>
int InterpolationSearch(int A[], int n, int x)
{
int low = 0;
int high = n - 1;
while (low <= high)
{
int mid = low + (((high - 1) * (x - A[low])) / (A[high] - A[low]));
if (x == A[mid])
return mid; // Found x, return (exit)
else if (x < A[mid])
high = mid - 1; // X lies before mid
else
low = mid + 1; // x lies after mid
}
return -1;
}
int main()
{
int A[] = {2, 4, 5, 7, 13, 14, 15, 23};
int x = 17;
int index = InterpolationSearch(A, 8, x); // passed array A inside the InterpolationSearch function
if (index != -1)
std::cout << "Number " << x << " is at " << index;
else
std::cout << "Number " << x << " not found";
}
// randomly set x bcoz array was defined by us , therefore not reasonable for asking input.
// We could have asked for input if array elements were inputed by the user.
```