Given a sorted array of integers and a target, find out if a target exists in the array or not. If target exists in the array, print index of it.

For example,

**Input: **

arr[] = [2, 3, 5, 7, 9]

target = 7

**Output: **Element found at index 3

**Input: **

arr[] = [1, 4, 5, 8, 9]

target = 2

**Output: **Element not found

**Interpolation search** is an algorithm similar to binary search for searching for a given target value in an sorted array. *It parallels how humans search through a telephone book for a particular name, the target value by which the book’s entries are ordered*.

We know that binary search always chooses the middle of the remaining search space, discarding one half or the other depending on the comparison result between the mid value & the target value and the remaining search space is reduced to the part before or after the mid position.

By comparison Interpolation search, at each search step, calculates where in the remaining search space the target might be present, based on the low and high values of the search space and the value of the target. The value actually found at this estimated position is then compared to the target value. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or after the estimated position. This method will only work if calculations on the size of differences between target values are sensible.

Interpolation search use below formula to calculate the mid position –

mid = low + ((x – A[low]) * (high – low) / (A[high] – A[low]));

Here, A[low..high] is our search space and x is the given target.

Below is the C++ implementation of interpolation search. At each iteration, it computes a mid position and then as with the binary search, moves either the upper or lower bound in to define a smaller interval containing the target value. Unlike the binary search which guarantees half search space size with each iteration, a poor interpolation may reduce/increase the mid index by only one, thus resulting in a worst-case efficiency of O(n).

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> using namespace std; // find out if a target x exists in the sorted array A // or not using Interpolation search algorithm int InterpolationSearch(int A[], int n, int x) { // search space is A[low..high] int low = 0, high = n - 1, mid; while (A[high] != A[low] && x >= A[low] && x <= A[high]) { // estimate mid mid = low + ((x - A[low]) * (high - low) / (A[high] - A[low])); // target value is found if (x == A[mid]) return mid; // discard all elements in the right search space // including the mid element else if (x < A[mid]) high = mid - 1; // discard all elements in the left search space // including the mid element else low = mid + 1; } // if target is found if (x == A[low]) return low ; // x doesn't exist in the array else return -1; } // main function int main() { int A[] = {2, 5, 6, 8, 9, 10}; int n = sizeof(A)/sizeof(A[0]); int target = 5; int index = InterpolationSearch(A, n, target); if (index != -1) cout << "Element found at index " << index; else cout << "Element not found in the array"; return 0; } |

**Output: **

Element found at index 1

**Performance**

Each iteration of the above code requires between five and six comparisons. On average the interpolation search makes about *log(log(n))* comparisons if the elements are uniformly distributed, where n is the number of elements to be searched. In the worst case it can make up to *O(n)* comparisons. Worst case might happen when the numerical values of the targets increase exponentially.

Note – *This article doesn’t not provide in-depth analysis of how interpolation search works but aims at providing just an overview of achieving better performance than binary search algorithm for a sorted array.*

**References:**

https://en.wikipedia.org/wiki/Interpolation_search

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂