This C program implements Interpolation search algorithm on array of integers. This is the technique more efficient than binary search.

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

`/*`

`* C Program for Interpolation search algorithm`

`*/`

`#include <stdio.h>`

`#define MAX 200`

`/* Inetrpolation search function */`

int interpolation_search(int a[], int bottom, int top, int item)

`{`

int mid;

while (bottom <= top) {

mid = bottom + (top - bottom) * ((item - a[bottom]) / (a[top] - a[bottom]));

if (item == a[mid])

return mid + 1;

if (item < a[mid])

top = mid - 1;

`else`

bottom = mid + 1;

`}`

return -1;

`}`

`/* End of interpolation_search() */`

`/* The main() begins */`

int main()

`{`

int arr[MAX];

int i, num;

int item, pos;

printf("\nEnter total elements (num< %d) : ", MAX);

scanf("%d", &num);

printf("Enter %d Elements in ascending order: ", num);

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

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

printf("\nSearch For : ");

scanf("%d", &item);

pos = interpolation_search(&arr[0], 0, num - 1, item);

if (pos == -1)

printf("\nElement %d not found\n", item);

`else`

printf("\nElement %d found at position %d\n", item, pos);

return 0;

`}`

$ gcc interpolation.c $ a.out Enter total elements (num< 200) : 10 Enter 10 Elements in ascending order: 1 5 9 12 16 18 25 56 76 78 Search For : 25 Element 25 found at position 7

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

If you wish to look at all C Algorithms and Solutions, go to C Algorithms.