Interpolation Search
On hearing about searching algorithm ,most of the Computer Science major students and professionals get remembered about linear search and then about binary search.On coding challenges, we mostly use linear search and if their is a requirement of reducing time complexity , we use binary search. But there are other kind of searches and one among them is Interpolation search, also known as Extrapolation search.
It is quite similar to binary search as both works on sorted array or list.
The concept of interpolation search is similar to how we used to search names in a telephone book or for keys by which a book’s entries are ordered. For example, when looking for a name “Bharat” in a telephone directory, we know that it will be near the extreme left so applying a binary search technique by dividing the list in two halves each time is not a good idea. We must start scanning the extreme left in the first pass itself .In each step of interpolation search the remaining search space of the value to be found is calculated .The calculation is done based on the values at the bound of the search space and the values to be searched the value found at the estimated position is then compared with the value being searched for. If the two values are equal then the search is complete however in the case of the values are not equal then depending on the comparison the remaining search space is reduced to the path before or after estimate position Thus, we see that interpolation search is similar to binary search technique.
Algorithm :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Interpolation_search(A,lower_bound,upper_bound,val)
Step 1: Initialise-set Low=lower_bound, High=upper_bound, Pos=-1;
Step 2: Repeat Steps 3 to 4 while Low≤High;
Step 3: Set Mid=Low+(High-Low)*((Val-A[Low])/(A[High]-A[Low]));
Step 4: If Val=A[Mid]{ Pos=Mid;Print Pos}; Go Step 6;
Else if Val<A[Mid]{Set High=Mid-1;}
Else {Set Low=Mid+1;}
[End of Loop]
Step 5: If Pos=-1 {Print “Value is not Present in the Array”}
Step 6: Exit.
— — — — — — — — — — — — — — — — — — — — — — — — — — — — —
However, the important difference between the two technique is that binary search always select the middle value of the remaining search space. It discuss half of the values based on the comparison between the value found at the estimated position and the values to be selected. But in interpolation search, interpolation is used to find an item near the one being searched for, and then linear search is used to find the exact item.
Complexity of Interpolation Search Algorithm:
When n elements of a list to be sorted are uniformly distributed average case, interpolation search makes about log (log n) comparison. However, in worst case, that is when the element increases exponentially, the algorithm can make up to O(n) comparison.
Program to demonstrate Interpolation search:
— — — — — — — — — — — — — — — — — — — — — — — — — — — —
import java.io.*;
import java.util.*;
class Interpolation{
// If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
public static 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 + (((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
public static void main(String[] args)
{
// 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 };
//If array not sorted use: Arrays.sort(arr);
int n = arr.length;
// Element to be searched
int x = 18;
int index = interpolationSearch(arr, 0, n — 1, x);
// If element was found
if (index != -1)
System.out.println(“Element found at index” + index);
else
System.out.println(“Element not found.”);
}
}
— — — — — — — — — — — — — — — — — — — — — — — — — — — —
