# 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 _{1},y_{1}) & (x_{2},y_{2})**, and the

**interpolant**is given by:

**y=y**

_{1}+(y_{2}-y_{1})(x-x_{1})/(x_{2}-x_{1}) 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.