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:
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
TOP Interview Coding Problems/Challenges