Interpolation Search Algo and its implemenation in java

Interpolation Search

The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. Binary Search always goes to middle element to check. On the other hand interpolation search may go to different locations according the value of key being searched.

For example if the value of key is closer to the last element, interpolation search is likely to start search toward the end side.

Linear Search finds the element in O(n) time,

Jump Search takes O(√ n) time and Binary Search take O(Log n) time.

The whole formula is:

// The idea of formula is to return higher value of pos
// when element to be searched is closer to arr[hi]. And
// smaller value when closer to arr[lo]

pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]

arr[] ==> Array where elements need to be searched
x     ==> Element to be searched
lo    ==> Starting index in arr[]
hi    ==> Ending index in arr[]

where lo,x and hi is an int value.

Step1: In a loop, calculate the value of “pos” using the probe position formula.
Step2: If it is a match, return the index of the item, and exit.
Step3: If the item is less than arr[pos], calculate the probe position of the left sub-array. Otherwise calculate the same in the right subarray.
Step4: Repeat until a match is found or the sub-array reduces to zero.

Sample Code:

class InterpolationApp
{
static int arr[] = new int[]{10, 12, 13, 16, 18, 19, 20, 21, 22, 23,24, 33, 35, 42, 47};

static int interpolationSearch(int x)
{
int lo = 0, hi = (arr.length - 1);

while (lo <= hi && x >= arr[lo] && x <= arr[hi])
{
int pos = lo + (((hi-lo) /
(arr[hi]-arr[lo]))*(x - arr[lo]));

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

public static void main(String[] args)
{
int x = 18;
int index = interpolationSearch(x);

if (index != -1)
System.out.println("Element found at index " + index);
else
System.out.println("Element not found.");
}

}

Output: Element found at index 4.

Time Complexity : 

If elements are uniformly distributed, then O (log log n)).
In worst case it can take up to O(n).


Auxiliary Space : O(1)