C program to implement interpolation search

This program implements interpolation search in c. Interpolation search makes log(log(n)) comparisons on average and O(n) comparisons in the worst case.Where  'n' is the number of elements to be searched. Interpolation search is used to search for a key value in an indexed array ordered by the values of the key.

Program

#include<stdio.h>

#include<conio.h>

void main()

{

int a[25],n,mid,low,high,f=0,item,i;

printf("Enter the size of the array");

scanf("%d",&n);

printf("Enter the elements in sorted order");

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

{

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

}

printf("Enter the item to be searched for");

scanf("%d",&item);

low=0;

high=n-1;

while(low<=high)

{

mid=(low+(high-low)*((item-a[low])/(a[high]-a[low])));

if(a[mid]==item)

{

printf("\n\nItem found at position %d",mid);

f=1;

break;

}

else if(a[mid]>item)

{

high=mid-1;

}

else

{

low=mid+1;

}}

if(f==0)

printf("\n\nItem not found in the array");

getch();

}