 # Interpolation Search

• Formula for Interpolation Search is =>  mid = l + ((h - l) / (arr[h] - arr[l])) * (key - arr[l]);

code is =>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define max 10
int main()
{
int arr[max],i,l,h,mid,key;
printf("Enter the elements into the array\n");
for(i=0;i<max;i++)
{
scanf("%d",&arr[i]);
}
printf("Enter the key value which you wan't to search\n");
scanf("%d",&key);
l=0;
h=max-1;
while(h>=l)
{
mid = l + ((h - l) / (arr[h] - arr[l])) * (key - arr[l]);
if(arr[mid]==key)
{
printf("element found at index arr[%d]\n",mid);
return 0;
}
else if(key<arr[mid])
{
h = mid - 1;
}
else
{
l = mid + 1;
}
}
printf("Key value is not present into the array\n");
return -1;
}

not working for only the series given below when find key value 12 or 13
1,3,5,7,9,11,15,16,17,18

• You can try this code with any type of series

===========================================================================
Program (code)
===========================================================================
#include<stdio.h>
#include<string.h>
#include<math.h>
struct bs
{
int key;
int l,h,m,i;
int a;
};
typedef struct bs bs;
int bin_s(bs);
int main()
{
int i;
bs b;
printf("enter the data\n");
for(i=0; i<10;i++ )
scanf("%d",&b.a[i]);
printf("enter the Key world\n");
scanf("%d",&b.key);
b.l=0;
b.h=9;
b.i=0;
b.m = bin_s(b);

printf("data found:= %d\n",b.m);
return -1;
}
//recursive function for interpolation search
int bin_s(bs b)
{
if(b.h >= b.l && b.i <= 10)
{
b.i=b.i+1;
b.m = b.l + ((b.h - b.l+1) / (b.a[b.h] - b.a[b.l]+1)) * (b.key - b.a[b.l]);
printf("b.m:= %d\n",b.m);
printf("b.i:= %d\n",b.i);
if(b.key == b.a[b.m])
{
return b.m;
}
else if(b.a[b.m] < b.key)
{
b.l=b.m + 1;
b.m = bin_s(b);
return b.m;
}
else
{
b.h= b.m - 1;
b.m = bin_s(b);
return b.m;
}

}