package interpolation;

// Driver method
    public static void main(String[] args)
    {
         Scanner s = new Scanner(System.in);
         int arr[] = new int[] {1,5,6,9,15};
         int search;
         int index=0;
         int count= 0;
         System.out.println("Enter Number To Search: ");
         search = s.nextInt();


             int low =0;
             int position;
             int high = (arr.length-1);

             while(low <= high && search >=arr[low] && search <= arr[high])
             {
                 position = low + (((high-low) / (arr[high]-arr[low]))*(search-arr[low]));
                // count++;
                 if(arr[position]==search)
                 {
                     index = position;
                 }
                 if(arr[position] < search)
                 {
                     low = position+1;
                 }
                 else
                 {
                     high = position-1;
                 }
                 count++;
             }

             if(index != -1)
             {
                 System.out.println("Number is Present at Index: "+index);
             }
             else
             {
                 System.out.println("Number is not present");
             }
             System.out.println(" "+count);



}