Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

Hello Ninjas, As you heard about different searching algorithms used in solving Data Structure and Algorithms based problems. Some algorithms are Logarithmic, while some are Linear Time Complexity. In the present scenario, Binary Search is the most widely used search Algorithm. Can we even perform better than Binary Search? Can we achieve time complexity less than simple Logarithmic? The answer is Yes. We can accomplish an even better Search Algorithm using Interpolation Search. Interpolation Search Algorithm is applied on Uniformly Sorted data and has less Time Complexity than the standard Binary Search Algorithm.

In this article, we will discuss Interpolation Search Algorithm. We will also review its Internal Working, Examples, Complexities and Implementation.

Definition

Interpolation Search is a search algorithm. It is used to find the target value in a given sorted range of values. It performs better than the normal binary search algorithm if the given range of sorted values is uniform. The difference between consecutive elements at each index should be identical or nearly identical.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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 -

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.

If Low > High, it means we covered all the elements in the array. We return -1 to acknowledge element 'Number' is not present.

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

If the above two conditions, 2 and 3, are not encountered, 'Number' may exist in the array. Now we can apply Interpolation Search Algorithm.

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;
}

Output

Time Complexity

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

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.

If the given input array is sorted and non-uniform, the Time Complexity will be O(n).

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.

Comparison Between Interpolation Search and Binary Search

Parameters

Interpolation Search

Binary Search

Estimation Method

It uses linear equations under the assumption that values are uniform.

It uses the divide and conquer approach and divides the search by half in each iteration.

Starting Point

Always find an index which tells the position nearer to the target and start with that point.

Always start with the mid index of the current range.

Time Complexity

O(log(logn)) in the best case. O(n) in the worst case

O(logn) in all the cases.

Space Complexity

O(1)

O(1)

Values Distribution

Uniform or near to Uniform.

Perform in all types of distribution.

Use Cases

It can be used in Database search, weather forecasting, scientific computing, image processing, and GIS.

It can be used in Searching and sorting algorithms, database management systems, and software engineering.

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.