Interpolation Search
In this tutorial, you will learn about interpolation search. Also, you will find working examples of interpolation search in C, C++, Java and Python.
Given a sorted array of n uniformly distributed elements, search for an element x in the array.
Linear Search will take O(n) time while Binary Search needs O(log n) time.
Interpolation Search offers an improvement over Binary Search for uniformly distributed values. Instead of always comparing with the middle element, Interpolation Search compares different positions, based on the value of the key being checked.
Position of element to be searched :-
The pos should be higher when x is closer to arr[high] and smaller when x is closer to arr[low]
pos = low + [ (x-arr[low])*(high-low) / (arr[high]-arr[low]) ]
arr[] ==> Array where elements need to be searched
x ==> Element to be searched
low ==> Starting index in arr[]
high ==> Ending index in arr[]
Interpolation Search Algorithm¶
1. Find pos using the above probe position formula
2. Compare x with arr[pos]
3. If it is a match, return pos
4. Else if x is greater than arr[pos], then x lies after pos. Repeat the process for the right subarray
5. Else x will lie before pos, so repeat the process for the left subarray
Recursive Implementation of Interpolation Search¶
// C program to implement interpolation search
// with recursion
#include <stdio.h>
// If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
int interpolationSearch(int arr[], int lo, int hi, int x)
{
int pos;
// Since array is sorted, an element present
// in array must be in range defined by corner
if( lo <= hi && x >= arr[lo] && x <= arr[hi])
{
// Probing the position with keeping
// uniform distribution in mind.
pos = lo + ( ( (double)( hi - lo ) /
( arr[hi] - arr[lo] ) ) * ( x - arr[lo] ) );
// Condition of target found
if( arr[pos] == x )
return pos;
// If x is larger, x is in right sub array
if( arr[pos] < x )
return interpolationSearch( arr, pos+1, hi, x);
// If x is smaller, x is in left sub array
if( arr[pos] > x )
return interpolationSearch( arr, lo, pos-1, x);
}
return -1;
}
// Driver Code
int main()
{
// Array of items on which search will
// be conducted.
int arr[] = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23,
24, 33, 35, 42, 47};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 18; // Element to be searched
int index = interpolationSearch(arr, 0, n-1, x);
// If element was found
if (index != -1)
printf("Element found at index %d", index);
else
printf("Element not found.");
return 0;
}
// C++ program to implement recursive Interpolation Search
#include <bits/stdc++.h>
using namespace std;
// A recursive interpolation search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int interpolationSearch(int arr[], int lo, int hi, int x)
{
int pos;
// Since array is sorted, an element present
// in array must be in range defined by corner
if( lo <= hi && x >= arr[lo] && x <= arr[hi])
{
// Probing the position with keeping
// uniform distribution in mind.
pos = lo + ( ( (double)( hi - lo ) /
( arr[hi] - arr[lo] ) ) * ( x - arr[lo] ) );
// Condition of target found
if( arr[pos] == x )
return pos;
// If x is larger, x is in right sub array
if( arr[pos] < x )
return interpolationSearch( arr, pos+1, hi, x);
// If x is smaller, x is in left sub array
if( arr[pos] > x )
return interpolationSearch( arr, lo, pos-1, x);
}
return -1;
}
int main(void)
{
// Array of items on which search will
// be conducted.
int arr[] = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23,
24, 33, 35, 42, 47};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 18; // Element to be searched
int index = interpolationSearch(arr, 0, n-1, x);
// If element was found
if (index != -1)
cout << "Element found at index " << index;
else
cout << "Element not found.";
return 0;
}
# Python3 program to implement
# interpolation search
# with recursion
# If x is present in arr[0..n-1], then
# returns index of it, else returns -1.
def interpolationSearch(arr, lo, hi, x):
# Since array is sorted, an element present
# in array must be in range defined by corner
if (lo <= hi and x >= arr[lo] and x <= arr[hi]):
# Probing the position with keeping
# uniform distribution in mind.
pos = lo + ((hi - lo) // (arr[hi] - arr[lo]) *
(x - arr[lo]))
# Condition of target found
if arr[pos] == x:
return pos
# If x is larger, x is in right subarray
if arr[pos] < x:
return interpolationSearch(arr, pos + 1,
hi, x)
# If x is smaller, x is in left subarray
if arr[pos] > x:
return interpolationSearch(arr, lo,
pos - 1, x)
return -1
# Driver code
# Array of items in which
# search will be conducted
arr = [ 10, 12, 13, 16, 18, 19, 20, \
21, 22, 23, 24, 33, 35, 42, 47 ]
n = len(arr)
# Element to be searched
x = 18
index = interpolationSearch(arr, 0, n - 1, x)
if index != -1:
print("Element found at index", index)
else:
print("Element not found")
// Java program to implement interpolation search
class Test
{
// Array of items on which search will
// be conducted.
static int arr[] = new int[]{10, 12, 13, 16, 18, 19, 20, 21, 22, 23,
24, 33, 35, 42, 47};
// If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
static int interpolationSearch(int x, int lo, int hi)
{
// Since array is sorted, an element present
// in array must be in range defined by corner
if (lo <= hi && x >= arr[lo] && x <= arr[hi])
{
if (lo == hi)
{
if (arr[lo] == x) return lo;
return -1;
}
// Probing the position with keeping
// uniform distribution in mind.
int pos = lo + (((hi-lo) /
(arr[hi]-arr[lo]))*(x - arr[lo]));
// Condition of target found
if (arr[pos] == x)
return pos;
// If x is larger, x is in upper part
if (arr[pos] < x)
lo = pos + 1;
// If x is smaller, x is in the lower part
else
hi = pos - 1;
return interpolationSearch(x, lo, hi);
}
return -1;
}
// Driver method
public static void main(String[] args)
{
int x = 18; // Element to be searched
int index = interpolationSearch(x, 0, arr.length);
// If element was found
if (index != -1)
System.out.println("Element found at index " + index);
else
System.out.println("Element not found.");
}
}
Iterative Implementation of Interpolation Search¶
// C program to implement interpolation search
#include<stdio.h>
// If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
int interpolationSearch(int arr[], int n, int x)
{
// Find indexes of two corners
int lo = 0, hi = (n - 1);
// Since array is sorted, an element present
// in array must be in range defined by corner
while (lo <= hi && x >= arr[lo] && x <= arr[hi])
{
if (lo == hi){
if (arr[lo] == x) return lo;
return -1;
}
// Probing the position with keeping
// uniform distribution in mind.
int pos = lo + (((double)(hi-lo) /
(arr[hi]-arr[lo]))*(x - arr[lo]));
// Condition of target found
if (arr[pos] == x)
return pos;
// If x is larger, x is in upper part
if (arr[pos] < x)
lo = pos + 1;
// If x is smaller, x is in the lower part
else
hi = pos - 1;
}
return -1;
}
// Driver Code
int main()
{
// Array of items on which search will
// be conducted.
int arr[] = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23,
24, 33, 35, 42, 47};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 18; // Element to be searched
int index = interpolationSearch(arr, n, x);
// If element was found
if (index != -1)
printf("Element found at index %d", index);
else
printf("Element not found.");
return 0;
}
// C++ program to implement interpolation search
#include<bits/stdc++.h>
using namespace std;
// If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
int interpolationSearch(int arr[], int n, int x)
{
// Find indexes of two corners
int lo = 0, hi = (n - 1);
// Since array is sorted, an element present
// in array must be in range defined by corner
while (lo <= hi && x >= arr[lo] && x <= arr[hi])
{
if (lo == hi)
{
if (arr[lo] == x) return lo;
return -1;
}
// Probing the position with keeping
// uniform distribution in mind.
int pos = lo + (((double)(hi - lo) /
(arr[hi] - arr[lo])) * (x - arr[lo]));
// Condition of target found
if (arr[pos] == x)
return pos;
// If x is larger, x is in upper part
if (arr[pos] < x)
lo = pos + 1;
// If x is smaller, x is in the lower part
else
hi = pos - 1;
}
return -1;
}
// Driver Code
int main()
{
// Array of items on which search will
// be conducted.
int arr[] = {10, 12, 13, 16, 18, 19, 20, 21,
22, 23, 24, 33, 35, 42, 47};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 18; // Element to be searched
int index = interpolationSearch(arr, n, x);
// If element was found
if (index != -1)
cout << "Element found at index " << index;
else
cout << "Element not found.";
return 0;
}
# Python program to implement interpolation search
# If x is present in arr[0..n-1], then returns
# index of it, else returns -1
def interpolationSearch(arr, n, x):
# Find indexs of two corners
lo = 0
hi = (n - 1)
# Since array is sorted, an element present
# in array must be in range defined by corner
while lo <= hi and x >= arr[lo] and x <= arr[hi]:
if lo == hi:
if arr[lo] == x:
return lo;
return -1;
# Probing the position with keeping
# uniform distribution in mind.
pos = lo + int(((float(hi - lo) /
( arr[hi] - arr[lo])) * ( x - arr[lo])))
# Condition of target found
if arr[pos] == x:
return pos
# If x is larger, x is in upper part
if arr[pos] < x:
lo = pos + 1;
# If x is smaller, x is in lower part
else:
hi = pos - 1;
return -1
# Driver Code
# Array of items oin which search will be conducted
arr = [10, 12, 13, 16, 18, 19, 20, 21, \
22, 23, 24, 33, 35, 42, 47]
n = len(arr)
x = 18 # Element to be searched
index = interpolationSearch(arr, n, x)
if index != -1:
print "Element found at index",index
else:
print "Element not found"
// Java program to implement interpolation search
class Test
{
// Array of items on which search will
// be conducted.
static int arr[] = new int[]{10, 12, 13, 16, 18, 19, 20, 21, 22, 23,
24, 33, 35, 42, 47};
// If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
static int interpolationSearch(int x)
{
// Find indexes of two corners
int lo = 0, hi = (arr.length - 1);
// Since array is sorted, an element present
// in array must be in range defined by corner
while (lo <= hi && x >= arr[lo] && x <= arr[hi])
{
if (lo == hi)
{
if (arr[lo] == x) return lo;
return -1;
}
// Probing the position with keeping
// uniform distribution in mind.
int pos = lo + (((hi-lo) /
(arr[hi]-arr[lo]))*(x - arr[lo]));
// Condition of target found
if (arr[pos] == x)
return pos;
// If x is larger, x is in upper part
if (arr[pos] < x)
lo = pos + 1;
// If x is smaller, x is in the lower part
else
hi = pos - 1;
}
return -1;
}
// Driver method
public static void main(String[] args)
{
int x = 18; // Element to be searched
int index = interpolationSearch(x);
// If element was found
if (index != -1)
System.out.println("Element found at index " + index);
else
System.out.println("Element not found.");
}
}
Interpolation Search Complexities¶
Time Complexity = O(log (log n))
Space Complexity = O(1) for Iterative Interpolation Search and O(log n) for Recursive Interpolation Search
Interpolation Search Applications¶
It is generally used when the array elements are sorted and uniformly distributed.