Interpolation Search Algorithm in Java

Author:
In this article, we will learn in details about the Interpolation Search algorithm.
Interpolation search is an algorithm for searching for a given key in an indexed array that has been ordered by numerical values assigned to the keys (key values). It parallels how humans search through a telephone book for a particular name, the key value by which the book's entries are ordered.

Position Probing in Interpolation Search

Interpolation search finds a particular item by computing the probe position. Initially, the probe position is the position of the middle most item of the collection.

If a match occurs, then the index of the item is returned. To split the list into two parts, we use the following method −
mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where −
   A    = list
   Lo   = Lowest index of the list
   Hi   = Highest index of the list
   A[n] = Value stored at index n in the list
If the middle item is greater than the item, then the probe position is again calculated in the sub-array to the right of the middle item. Otherwise, the item is searched in the subarray to the left of the middle item. This process continues on the sub-array as well until the size of subarray reduces to zero.
Runtime complexity of interpolation search algorithm is Ο(log (log n)) as compared to Ο(log n) of Binary Search Algorithm in favorable situations.

Interpolation Search Implemenation in Java

/**
 * Interpolation search is an algorithm for searching for a given key in an indexed array.
 * @author Ramesh Fadatare
 */
public class InterpolationSearch {

    private static int[] sorted = null;

    // Assuming the array is sorted
    public static final int find(int value, int[] array) {
        InterpolationSearch.sorted = array;
        try {
            return recursiveFind(value, 0, InterpolationSearch.sorted.length - 1);
        } finally {
            InterpolationSearch.sorted = null;
        }
    }

    private static int recursiveFind(int value, int start, int end) {
        if (start == end) {
            int lastValue = sorted[start]; // start==end
            if (value == lastValue)
                return start; // start==end
            return Integer.MAX_VALUE;
        }

        final int mid = start + ((value - sorted[start]) * (end - start)) / (sorted[end] - sorted[start]);
        if (mid < 0 || mid > end)
            return Integer.MAX_VALUE;
        int midValue = sorted[mid];
        if (value == midValue)
            return mid;
        if (value > midValue)
            return recursiveFind(value, mid + 1, end);
        return recursiveFind(value, start, mid - 1);
    }
    
    public static void main(String[] args) {
      int[] integers = {10,20,30,40,50,60,70,80,90,100};

         //the element that should be found
         int key = 100;

         InterpolationSearch search = new InterpolationSearch();
         int atIndex = search.find(key, integers);
         
         System.out.println("Remember array index starts from 0");
         System.out.println("The size of the array is : " + integers.length);
         System.out.println("The element found at index : " + atIndex);
 }
}
Output:
Remember array index starts from 0
The size of the array is : 10
The element found at index : 9

Reference

Master in Data Structures and Algorithms in Java
Learn Complete Java Programming on Java Tutorial | Learn Java Programming with Examples

Comments

Post a Comment