IndexSequential, InterPolation Search

#include<stdio.h>
#include<conio.h>
int index_sequential(int a[],int,int);
int interpolation_search(int a[],int,int);
void main()
{
  int a[100],n,i,x,key,j;
  clrscr();
  printf("Enter the no. of elements:> \n");
  scanf("%d",&n);
  printf("\nEnter the elements of the array: \n");
  for(i=0;i<n;i++)
  {
    scanf("%d",&a[i]);
  }
  printf("\nEnter the element to be serched : ");
  scanf("%d",&key);
  printf("\n1.Index sequential search.\n2.Interpolation search.\n");
  scanf("%d",&x);
  switch(x)
  {
    case 1:j=index_sequential(a,n,key);  break;
    case 2:j=interpolation_search(a,n,key);  break;
    default :printf("\nEnter a valid number....");
  }
  if(j==-1)
  {
    printf("\nElement is not found..");
  }
  else
  {
    printf("\nElement is found at position : %d",j);
  }
  getch();
}
int index_sequential(int a[],int n,int key)
{
  int keys[6],index[6],i,j,temp,n1,start;
  for(i=1;i<n;i++)
  {
   for(j=0;j<n-1;j++)
   {
    if(a[j]>a[j+1])
    {
     temp=a[j];
     a[j]=a[j+1];
     a[j+1]=temp;
    }
   }
  }
  n1=0;
  for(i=0;i<n;i=i+4)
  {
    keys[n1]=a[i];
    index[n1]=i;
    n1++;
  }
  if(key<keys[0])
    return(-1);
  for(i=0;i<n1;i++)
  {
    if(key<keys[i])
      break;
  }
  start=index[i-1];
  for(i=start;i<start+4&&i<n;i++)
  {
    if(a[i]==key)
      return(i);
  }
  return(-1);
}
int interpolation_search(int a[],int n,int key)
{
  int i=0,j=n-1,mid;
  mid=i+(j-i)*(key-a[i])/(a[j]-a[i]);
  while(a[mid]!=key&&i<=j)
  {
    if(key<a[mid])
    {
      j=mid-1;
    }
    else
    {
      i=mid+1;
    }
    mid=i+(j-i)*(key-a[i])/(a[j]-a[i]);
  }
  if(a[mid]==key)
  {
    return mid;
  }
  else
    return -1;
}

/*Output:
Enter the no. of elements:>
5

Enter the elements of the array:
1 2 3 4 5

Enter the element to be serched : 5

1.Index sequential search.
2.Interpolation search.
1

Element is found at position : 4
——–
Output:
Enter the no. of elements:>
5

Enter the elements of the array:
1000
2000
3000
4000
5000

Enter the element to be serched : 4000

1.Index sequential search.
2.Interpolation search.
2

Element is found at position : 3
*/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s