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.

Interpolation Search Example

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

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.