Signup/Sign In

Interpolation Search Algorithm

Posted in Programming   NOVEMBER 22, 2021

    No question Binary Search is one the greatest searching algorithms offering average runtime of O(log n), but still, there are circumstances when more efficient searching may be conducted.

    Let’s describe one such example.

    Consider two arrays:

    • Array 1: 1 3 8 9 12 14 27 29 34 37
    • Array 2: 10 20 30 40 50 60 70 80 90 100 110 120


    Both of the preceding arrays are sorted in ascending order, however, if you look attentively Array 1 is not uniformly distributed, whereas Array 2 is uniformly distributed, that is, the items in Array 2 are arranged in regular intervals of equal size, in our example 10.

    Now if we want to seek element 110 in Array 2, and we proceed by the standard binary search it will first choose the middle element and then reach 110 splitting the array into half each time.

    What is Interpolation S?


    Interpolation is a mathematical word, which is simply a procedure of estimating an intermediate value given some sequence of discrete data.

    Understanding Interpolation Search


    Interpolation search is an optimized variation of vanilla Binary Search, which is best suited for evenly distributed variables.

    Almost the whole algorithm is identical to that of binary search, except picking the pivot point or probe which is picked dependent on the value being sought.

    Interpolation Sarch

    Interpolation Search Algorithm

    • Find the probe using the formula
    • Compare it with the data
    • If the value is matched, return success
    • If the value is smaller, choose the left sub-array and repeat steps from commencing
    • If the value is bigger, choose the correct sub-array and repeat steps from commencing
    • Repeat the preceding steps, if the element is discovered return success else return failure

    The above approach works for items sorted in ascending order, for descending order if the value is bigger choose the left sub-array and vice versa.

    Example

    Consider the Array: 7 10 13 17 20 23 26 29 32

    Element to search: 29

    interpolation search

    Now we will find the probe using the formula.

    Initially 
    
    low=0, high=8
    
    mid = 0 + (((8-0)/(32-7))*(29-7))
    
    mid = 6

    In this situation, we can see that the probe is right-biased since the needed value is on the right side of the array, similarly, if the value would have been on the left side of the array, the probe value would have been left-biased.

    interpolation search

    low=7, high=8
    
    mid = 7 + (((8-7)/(32-29))*(29-29))
    
    mid = 7

    Here arr[mid] = 29 which is the needed element, so we converge to the result in only two passes.

    Now let’s take a look at the Java code for Interpolation Search.

    public class Searching {
    
        boolean interpolationSearch(int arr[], int n) {
            int lengthOfArray = arr.length;
            int mid; // to store middle element
            int low = 0;
            int high = lengthOfArray - 1;
            while (low <= high) {
                mid = low + (((high - low) / (arr[high] - arr[low])) * (n - arr[low])); // Formula for finding the pivot point or probe
    
                if (arr[mid] == n) {
                    return true;
                } else if (arr[mid] < n) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            return false;
    
        }
    
        // Driver Code
        public static void main(String args[]) {
            Searching search = new Searching();
            int arr[] = {
                12,
                16,
                25,
                37,
                46,
                55,
                76,
                86
            };
            if (search.interpolationSearch(arr, 76)) {
                System.out.println("Element found !");
            } else {
                System.out.println("Element not found :( ");
            }
    
        }
    }

    Performance

    Case Runtime
    Best O(1)
    Average O(log(log n))
    Worst O(n)
    Auxiliary Space O(1)

    Interpolation search works best when the data are equally distributed and can converge to the solution in an average runtime of O(log (log n)).

    About the author:
    Adarsh Kumar Singh is a technology writer with a passion for coding and programming. With years of experience in the technical field, he has established a reputation as a knowledgeable and insightful writer on a range of technical topics.
    Tags:interpolation-searchalgorithm
    IF YOU LIKE IT, THEN SHARE IT
     

    RELATED POSTS