Interpolation Search

rohitjangra096

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

ankitkhasa543

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[10];
};
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;
                }

        }
        printf("key not found\n");
        return -1;
}

==================================================================
                                            Try it with any series
==================================================================

rohitjangra096

I tried with make some changes in the formula and i got a solution for Interpolation search,Now my code works for all the series of sorted elements.
Edited Formulas =>
mid = l + ((h - l+1) / (*(ptr+h) - (*(ptr+l)+1))) * (key - *(ptr+l));
and,
previous formula is =>
mid = l + ((h - l) / (*(ptr+h) - (*(ptr+l))) * (key - *(ptr+l));

rohitjangra096

When both high(h) and low(l) become equal then compiler show Floating point exception. so to overcome from this situation i incremented value of l by 1....

Interpolation Search

Howdy, Stranger!

Categories