Home » Code Snippets » C/C++ Data Structure programs

C program to implement Interpolation Search Algorithm

Interpolation Search Algorithm implementation using C program: Here, we are going to learn about the Interpolation Search Algorithm, how it works, and its C language implementation.
Submitted by Sneha Dujaniya, on May 09, 2020

Problem:

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

Solution:

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

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]) }
```

Basic Algorithm:

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)

C Implementation:

#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