Interpolation Search

Internal Working

In the case of Binary Search, we generally start from mid. But in the case of Interpolation Search, since we know that given sorted values are uniform, we can find an appropriate index to start. The probability of finding a relative position of an element is higher in uniform sorted values.

Let takes an example for better understanding. 

Suppose we have an array of numbers ranging from 1 to 100, with a sequential difference of 2.

• The above figure shows smaller numbers like 1, 3, and 5 at the beginning. 
   
• The more significant numbers like 99, 97 and 95 will be found at the end of the list. 
   
• Also, the mid-range numbers like 51, 53 and 55 will be found in the middle of the list.
   

Suppose we want to find an index of the number 75; we can easily find the close index range of this number using some mathematical calculations. 

Mathematical Approach

As discussed, we can find the approximate position using a mathematical approach. Since values are uniform and can be represented in a Straight Line. The Linear Equation of two Variables is -

y = m*x + c

where,
x is the coordinate along the horizontal axis
y is the coordinate along the vertical axis
m is the slope of the line
c is a constant.

We can come up with a linear equation as shown below -
A[index] = m*index + c

where,
index is the position of the element in the array
A[index] is the value at this index in the array

Let's put the knows points to get unknown parameters. Here our unknown parameters are slope(m) and coefficient(c).
A[low] = m * low + c …………………………………… (1)
A[high] = m * high + c …………………………………. (2)

Let's say we are trying to search for an element 'Number' in this array. Then in the above equation, we get
Number = m * index + c ………………………………..(3)
where the index is the probable position of 'Number' in this array.

subtracting equation 1 from 2, we get
A[high] – A[low] = m * (high – low)
m = (A[high] – A[low]) / (high – low) …………………. (4)

Now subtracting equation 1 from 3, we get
Number – A[low] = m * (index – low)
index – low = (Number – A[low]) / m
index = low + (Number – A[low]) / m

Replacing the value of m from equation 4 above, we get
index = low + ( Number - arr[low] ) * ( high - low ) / ( arr[high] - arr[low] )

Algorithm

Below is the description of the Interpolation Search Algorithm -

1. Initialize an array 'arr' of size n. Let low and high be two-pointer of an array. Here, the high point is to the last accessing element, and the low point is to the first not yet accessed. Initially, high = n - 1 and low = 0; we need to find the 'Number' in an array.
    
2. If Low > High, it means we covered all the elements in the array. We return -1 to acknowledge element 'Number' is not present.
    
3. If Number < arr[low] or Number > arr[high], we can directly return -1. As the array is sorted, 'Number' should lie between arr[low] and arr[high].
    
4. If the above two conditions, 2 and 3, are not encountered, 'Number' may exist in the array. Now we can apply Interpolation Search Algorithm.
    
5. Initialize the index using the above-derived mathematical equation. 
   
   Hence index = index = low + (Number - arr[low]) * (high - low) / (arr[high] - arr[low] ). 
   
   There will be three cases in Binary Search. Those are as follows -
    

• Case - 1: If arr[index] < Number, It means the desired element is greater than the currently selected index and present in a higher value subset of that range(index, high). Therefore low = index + 1.
   
• Case - 2: If arr[index] > Number, It means the desired element is less than the currently selected index value and present in a lower value subset of that range(low, index). Therefore high = index - 1.
   
• Case - 3: If arr[index] = Number. Return the index value in this case, i.e. return index.

Dry Run

Below is a demonstration of the Interpolation Search Algorithm using an Example -

Let the input array A = [5, 10, 14, 18, 22, 27]

Therefore, N = 6, high = 5, low = 0, Number(target value) = 18

In our case, 18 > A[low] and 18 < A[high] as prescribed in Step 3. This means a solution may exist in the given Array A.

Now after passing into the while loop of the Interpolation Search Algorithm, we get -

Iteration - 1: Let index = low + ( Number - arr[low] ) * ( high - low ) / ( arr[high] - arr[low] )

index = 0 + (18 - 5) * (5 - 0) / (27 - 5)

index = 2(rounded to floor value), as shown in below image.

According to the condition, if A[index] < Number, then low = index + 1. I.e. index =  3.
 

Iteration - 2: Since low < high, Again, we continue the loop and calculate the index.

index = 3 + (18 - 18) * (5 - 3) / (27 - 18)

index = 3(rounded to floor value), as shown in the below image.

According to the condition, if A[index] = Number, returns the index to the user. In this iteration, we got the target(18) found at index = 3, returning 3 to the answer, Exit.

C++ Code Implementation

#include <bits/stdc++.h>
using namespace std;

int Interpolation_Search(int *A, const int &n, const int &Number)
{
    int low = 0;
    int high = n - 1;
    
    // Checking for the condition described in Step - 3 of Algorithm.
    if(Number < A[low] || Number > A[high])
            return -1;
    while (low < high)
    {
        // Calculating near index.
        int index = low + (Number - A[low]) * (high - low) / (A[high] - A[low]);

        // If match then return the index.
        if (A[index] == Number)
            return index;

        // If smaller, then target shift low to larger subset.
        else if (A[index] < Number)
            low = index + 1;

        // If greater then target shift high to smaller subset.
        else
            high = index - 1;
    }

    // If target not found.
    return -1;
}

int main()
{
    // For fast input/ouput.
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Initializing array and target value.
    int  A[6] = {5, 10, 14, 18, 22, 27};
    int n = 6;
    int Number = 18;

    // Calling interpolation search algorithm.
    int Result = Interpolation_Search(A, n, Number);
    if (Result == (-1))
        cout << "Element Not Found!!\n";
    else
        cout << "Element Found at Index: " << Result << '\n';
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Time Complexity

The Time Complexity of the Interpolation Search depends on two cases -

1. If the given input array is sorted and uniform, the Time Complexity will be O(log(logn)). Here the base of the log is 2.
    
2. If the given input array is sorted and non-uniform, the Time Complexity will be O(n).

Read More - Time Complexity of Sorting Algorithms

Space Complexity

O(1): In Interpolation Search Algorithm, we are not creating any extra space.

Hence Time Complexity is O(1).

Applications of Interpolation Search

Below are the Applications of the Interpolation Search Algorithm -

Database Search

In Database, records are indexed by key values. The key value in Database is unique and sorted in ascending order and uniform. Therefore we can use Interpolation Search Algorithm for faster querying.

Image Processing

In Image Processing, the number of pixels changes when an image is scaled or resized. We can use Interpolation Search Algorithm to find the colour values of new pixels based on neighbouring pixels.

Phone Book Search

In Phone Book, contacts are arranged in sorted order and nearly uniform. Therefore, we can apply Interpolation Search Algorithm for fast retrieval of contacts.

For Solving Competitive Programming Problems

Highly efficient search algorithms are required in Competitive Programming because of the small time limit and significant value constraint. Therefore we can use Interpolation Search Algorithm, which can perform searching more efficiently than Binary Search Algorithm.

Must Read Algorithm Types

Comparison Between Interpolation Search and Binary Search 

Frequently Asked Questions

Define Interpolation Search Algorithm.

Interpolation Search Algorithm is a fast searching-based algorithm applied in a sorted and uniform array of values. It estimates the index nearer to the target index's position on each iteration.

What is the Time Complexity of the Interpolation Search Algorithm?

The Time Complexity of the Interpolation Search Algorithm is variable and depends on two cases. In the best case, when the array values are sorted and uniform, have O(log(logn)). In the worst case, it can have O(n).

What are the Limitations of the Interpolation Search Algorithm?

One of the significant drawbacks of the Interpolation Search Algorithm is its inconsistency. It does not always perform better. In non-uniform values of the array, it can go to O(n) Time complexity.

How is Interpolation Search different from Binary Search?

Interpolation Search Algorithm has a working model similar to Binary Search Algorithm. Only the major difference is starting index position. In Binary Search, the mid-position is chosen. In Interpolation Search, estimation is used to find the index.

What is the advantage of Binary Search over Interpolation Search?

There is one significant advantage of Binary Search over Interpolation Search. Binary Search performs well and more quickly in non-uniform values of the array, while Interpolation Search does not.

Conclusion

In this article, we discussed the Interpolation Search Algorithm. We went through their Internal Working, Pseudocode, Examples and Applications. We learned their comparison with their alternatives. We hope you enjoyed this article.

You can visit our other related blogs for more information on these topics.

• Time & Space Complexity of Searching Algorithms
• Introduction To Binary Search Algorithm
• Difference between Linear Search and Binary Search
• Binary Search in C++ Standard Template Library (STL)

You can also consider our Competitive Programming Course to give your career an edge over others!