Interpolation search (sometimes referred to as extrapolation search) is an algorithm for searching for a given key value in an indexed array that has been ordered by the values of the key. On average the interpolation search makes about log(log(n)) comparisons (if the elements are uniformly distributed), where n is the number of elements to be searched. In the worst case (for instance where the numerical values of the keys increase exponentially) it can make up to O(n) comparisons.

Here is the source code of the C program to search an element in an array using Interpolation Search Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`#include <stdio.h>`

`#include <stdlib.h>`

int interpolationsearch(int sortedArray[], int toFind, int len)

`{`

int low = 0;

int high = len - 1;

int mid;

while (sortedArray[low] <= toFind && sortedArray[high] >= toFind)

`{`

if (sortedArray[high] - sortedArray[low] == 0)

return (low + high)/2;

mid = low + ((toFind - sortedArray[low]) * (high - low)) / (sortedArray[high] - sortedArray[low]);

if (sortedArray[mid] < toFind)

low = mid + 1;

else if (sortedArray[mid] > toFind)

high = mid - 1;

`else`

return mid;

`}`

if (sortedArray[low] == toFind)

return low;

`else`

return -1;

`}`

int main()

`{`

int arr[200], len, number, i, pos;

printf("How many elements you want to enter: ");

scanf("%d", &len);

printf("\nEnter %d elements in increasing order: ", len);

for (i = 0; i < len; i++)

`{`

scanf("%d", &arr[i]);

`}`

printf("\nEnter an element to search: ");

scanf("%d", &number);

pos = interpolationsearch(arr, number, len);

if (pos != -1)

printf("\nElement found at postion %d . ", pos);

`else`

printf("\nElement NOT found!!!");

return 0;

`}`

$ gcc interpolation.c -o interpolation $ ./interpolation How many numbers you want to enter: 5 Enter 5 numbers : 34 45 67 77 89 Enter an element to search: 67 Element found at positon 2 .

**Sanfoundry Global Education & Learning Series – 1000 C Programs.**

Here’s the list of Best Reference Books in C Programming, Data Structures and Algorithms.