Home » Algorithms

Interpolation search algorithm

In this article, we are going to learn interpolation search along with its algorithm, C++ program.
Submitted by Radib Kar, on November 19, 2018

Binary search vs Interpolation search

Though binary search is a great algorithm for searching with average time complexity only logn, interpolation search is found to be more efficient as per as time complexity is considered.

In binary search, it often chooses the middle of the remaining search space, discarding one half or the other, again depending on the comparison between the key value found at the middle position and the key value is sought. Where in interpolation search, we use the concept of interpolation. Interpolation is a process of constructing new data point from an already given set of discrete points.

Interpolation

In computer science, one often has a number of data points which represent the values of a function for a limited number of values of the independent variable.

Linear interpolation takes two data points, say(x₁,y₁) & (x₂,y₂), and the interpolant is given by: y=y₁+(y₂-y₁)(x-x₁)/(x₂-x₁) at point (x,y)

Interpolation search

This algorithm tries to follow kind of searching as we search in the dictionary. Like, we need to search a word 'include' we start before the middle, but when we need to search 'test', we start searching from last. That means it's not necessary to partition the search space on basis of the only the middle element. This is because we know the words are ordered and our intuition says the binary search is a bad choice.

The interpolation search tries to improve the binary search, but the question is how to find the value. We know the bounds of the interval & we want to search closer to the searching element. This can be done using the formula: K= (data-low)/(high-low)

This K is a constant which helps us to narrow down the search space. For binary search K is simply=(low+high)/2

It's found that on an average interpolation search makes only log(logn) comparison to reach the searched element.

When to use interpolation search?

Data set( array elements) is ordered & uniformly distributed.

C++ implementation of interpolation search

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

void interpolationSearch(int* a,int n,int data){
	int low=0,k,high=n-1;
	while(low<=high){
		k=low+(((data-a[low])*(high-low))/(a[high]-a[low]));
		if(data==a[k]){
			cout<<"data found"<<endl;
			return;
		}
		if(data<a[k])
			high=k-1;
		else
			low=k+1;
	}
	cout<<"data not found"<<endl;
	
	return;
}

int main(){

	int n,data;

	// enter array length
	cout<<"enter no of elements\n";
	cin>>n;

	int* a=(int*)(malloc(sizeof(int)*n));

	//fill the array
	cout<<"enter elements................\n";
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	
	cout<<"enter element to be searched"<<endl;
	cin>>data;

	interpolationSearch(a,n,data);

	return 0;
}

Output

First run:
enter no of elements 
7
enter elements................ 
5
10 
15 
19 
24 
31 
37 
enter element to be searched 
10 
data found

---------------------------------
Second run:
enter no of elements 
6
enter elements................ 
23 
-11
45 
78 
-12
4
enter element to be searched 
12 
data not found