INTERPOLATION SEARCH

import java.util.Scanner;

class interpolationsearch
 {
  public static void main(String[] args)
  {
   int i,j,start,end,mid,n,item,temp,flag=0;
   Scanner is = new Scanner(System.in);
   System.out.println("Enter Size Of Array :");
   n=is.nextInt();
   int[] a;//declaration of array
   a=new int[n]; // Creation of array with given size
   System.out.println("Enter unsorted Array :");
   for(i=0;i<n;i++)
    {
     System.out.printf("\n Element a[%d]  :",i);
     a[i]=is.nextInt();
    }
  
   for(i=0;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;
        }
      }
    }
   System.out.print("\n Sorted Array elements :");
   for(i=0;i<n;i++)
     {
      System.out.print( a[i] +" ");
     }

   for(i=0;i<n;i++)
    {
     System.out.printf("\n ADDRESS=%h ---- ARRAY=a[%d]----- DATA=%d --- location=%d\n",i*4,i,a[i],i+1);
    }
   System.out.print("\n Enter the element to be searched :");
   item=is.nextInt();
   start=0;end=n-1;
      while(start <= end)
       {
        mid= start + (end - start) * ((item-a[start])/(a[end]-a[start]));
        if(item < a[mid])
          end=mid - 1;
        else if(item > a[mid])
          start=mid + 1;
        else if(item == a[mid])
          {
           System.out.printf("\n Element %d is found at location %d",item,mid+1);
           flag=1;
           break;
          }
       }
   
   if (flag==0)
      System.out.printf("\n Element %d is not in the array",item);
 }
}

output: