C program to implement interpolation search algorithm

Interpolation Search Algorithm: In this tutorial, we will learn about the Interpolation Search Algorithm, how it works, and the implementation of the interpolation search algorithm using the C program. By Sneha Dujaniya Last updated : August 10, 2023

Interpolation Search

Interpolation Search is a much better choice of search algorithm than Linear and Binary Search. We can perform a linear search on a very small dataset, a binary search on a large dataset but what if we are given a dataset where we have millions of data rows and columns. Here, the interpolation search comes to the rescue.

One of the basic assumptions of this algorithm is similar to that of the Binary Search Algorithm, i.e. the list of elements must be sorted and uniformly distributed.
It has a huge advantage of time complexity over binary search as here, the complexity is O(log log n) whereas, it is O(log n) in binary search in the average case scenario.

    Input:
    Array: 10, 20, 35, 45, 55, 68, 88, 91
    Element to be searched: 68

Terminologies

ub : upper index of the array
lb : lower index of the array
x : element to be searched
pos : the position at which the array is split and is calculated using the following formula,
```
    pos = lb + { [ (ub – lb) / (arr[ub] – arr[lb]) ] * (x – arr[lb]) }
```

Algorithm

The steps to implement interpolation search algorithm are:

Find the value of pos using the above formula
Compare the pos element with the element to be searched
If the value matches, return the index
Else if x is less than the pos element, new sub-array is the elements before the pos element, and if more than the pos value, then the upper half of the array is a new sub-array.
Repeat steps 1-4 till the target is reached or when there are no elements left.

Time Complexity

The time complexities of Interpolation Search Algorithm are,

Worst case: O(n)
Average Case: O(log log n)
Best case: O(1), when the element is present at pos itself
Space Complexity: O(1)

Problem statement

We are given an array arr[] with n elements and an element x to be searched amongst the elements of the array.

Here, we will be performing Interpolation Search to find the element in the array.

C program to implement interpolation search algorithm

#include <stdio.h>

int interpol_search(int arr[], int lb, int ub, int x)
{
    while ((arr[lb] != arr[ub]) && (x <= arr[ub]) && (x >= arr[lb])) {
        int pos = lb + (((ub - lb) / (arr[ub] - arr[lb])) * (x - arr[lb]));
        if (arr[pos] == x)
            return pos;
        if (arr[pos] < x)
            lb = pos + 1;
        else
            ub = pos - 1;
    }
    return -1;
}

int main()
{
    int arr[] = { 10, 20, 35, 45, 55, 68, 88, 91 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 68;
    int index = interpol_search(arr, 0, n - 1, x);
    if (index != -1)
        printf("Element %d is present at index %d", x, index);
    else
        printf("Element %d not found in the list!", x);

    return 0;
}

Output

Element 68 is present at index 5