C - Program to Implement Interpolation Search
#include <stdio.h>
#include <stdlib.h>
#define MAX 200
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;
}
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 : ", num);
for (i = 0; i < num; i++)
scanf("%d", &arr[i]);
printf("\nELEMENTS ARE\n: ");
for (i = 0; i < num; i++)
printf("%d\t", arr[i]);
printf("\nSearch For : ");
scanf("%d", &item);
pos = interpolation_search(&arr[0], 0, num, item);
if (pos == -1)
printf("\nElement %d not found\n", item);
else
printf("\nElement %d found at position %d\n", item, pos);
return 0;
}
