In this tutorial you will learn about the Interpolation Search Algorithm and its application with practical example.
What Is Interpolation Search Algorithm?
Interpolation search is an efficient search algorithm for finding an item in a sorted list of items. Interpolation search algorithm works only on a sorted list of elements. In order to search an element using interpolation search algorithm, we must ensure that the list is sorted and evenly distributed. Interpolation search algorithm is a combination of both binary search and linear search algorithms. Interpolation search, also called as extrapolation search.
Interpolation Search Program In C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <stdio.h> int interpolation_search(int a[], int low, int high, int val) { int mid; while(low <= high) { mid=low + (high-low) * ((val - a[low]) / (a[high] - a[low])); if(val == a[mid]) return mid; if(val < a[mid]){ high = mid - 1; } else{ low = mid + 1; } } return -1; } int main() { int a[30], ctr, n, val, loc; printf("Enter number of elements in array:\n"); scanf("%d", &n); printf("Enter %d integer numbers in ascending order:\n", n); for (ctr = 0; ctr < n; ctr++) scanf("%d", &a[ctr]); printf("Enter a number to search:\n"); scanf("%d", &val); loc = interpolation_search(a, 0, n-1, val); if(loc == -1) printf("%d is not present in the list.\n", val); else printf("%d is found at location %d.\n", val,loc+1); return 0; } |
Output:-
