Interpolation Search

  1. Interpolation Search Algorithm
  2. Interpolation Search Example
  3. Interpolation Search Algorithm Implementation
  4. Interpolation Search Algorithm Complexity

Interpolation search is a fast and efficient searching algorithm. It improves the binary search algorithm for scenarios where array elements are uniformly distributed over the sorted array. It works on the probing position of the required value. Unlike binary search, it does not always go to the middle of the array but may go to any position depending on the value of the key to be searched. We compare the value at the estimated position and reduce the search space to the part after or before it. For example, when we search a word in the dictionary, we flip pages according to the position of letters inside it and not by splitting search space into two halves every time.

Interpolation Search Algorithm

Let us assume that we have an unsorted array A[] containing n elements and we want to find a given element X.

  • Set lo as 0 , mid as -1 and hi as n-1.
  • While lo <= hi and X lies in the range between lo and hi, i.e. X >= A[lo] and X <= A[hi].
    • Calculate mid by using the formula for probe position - mid = lo + (X - A[lo]) * (hi - lo) / (A[hi] - A[lo])
    • If the element at probe position is less than target element move to right. If A[mid] < X set lo as mid + 1.
    • Else if the element is greater than the target element then move to left. If A[mid] > X, set hi as mid-1.
    • Else we have found the element and return mid
  • If lo == hi , only one element is remaining check if it is the target element i.e. if A[lo]==X.
    • If true, then return lo.
    • Else return -1.

Interpolation Search Example

Suppose we have the array: (1, 3, 7, 8, 11, 15, 17, 18, 21), and we want to find X - 18.

  • Set lo = 0 , mid= -1 and hi = 8.
  • Calculate mid as 6 by using the formula - 0 + (18 - 1)*(8 - 0)/(21-1).
  • Then we compare A[6] with X to see it is smaller and set lo as 7.
  • Calculate mid using 7 + (18 - 18)*(8 - 7)/(21 - 18).
  • Then we compare A[7] with X to see it is equal to 18 and return the index 7.

Interpolation Search Algorithm Implementation

#include <bits/stdc++.h>
using namespace std;

int interpolation_search(int arr[], int n, int X)
{
    int lo = 0;
    int hi = n - 1;
    int mid;

    while ((arr[hi] != arr[lo]) && (X >= arr[lo]) && (X <= arr[hi])) {
        mid = lo + ((X - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));

        if (arr[mid] < X)
            lo = mid + 1;
        else if (X < arr[mid])
            hi = mid - 1;
        else
            return mid;
    }

    if (X == arr[lo])
        return lo ;
    else
        return -1;
}

int main(void)
{
    int n = 9;
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int x = 4;
    int result = interpolation_search(arr, n, x);
    if (result == -1) {
        cout << "Element not found !!";
    }
    else cout << "Element found at index " << result;
    return 0;
}

Interpolation Search Algorithm Complexity

Time Complexity

  • Average Case

The algorithm’s average-case time complexity is of the order of O(log(logn)). It happens when all the elements inside the array are uniformly distributed.

  • Best Case

The best-case occurs when the element we are searching for is the first element probed by interpolation search. The best-case time complexity of the algorithm is O(1).

  • Worst-Case

The worst-case occurs when the numerical values of the targets increase exponentially. The worst-case time complexity of the algorithm is O(n).

Space Complexity

This algorithm’s space complexity is O(1) because it doesn’t require any data structure other than temporary variables.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Search Algorithm

  • Jump Search