Following is the function for interpolation search. This searching algorithm estimates the position (index) of a key in array based on the elements in the first position and last position in the...

Following is the function for interpolation search. This searching algorithm estimates the position (index) of a key in array based on the elements in the first position and last position in the array, and the length of array. The array must be sorted in ascending order.

Suppose array A contains the following 15 elements:

A = [1, 3, 3, 10, 17, 22, 22, 22, 24, 25, 26, 27, 27, 28, 28]

1. At first iteration, at which position (index) the element of 24 is estimated in array A?


2. In which part of array (starting index and ending index) the searching should continue?


3. How many iterations the searching are performed until the element of 24 is found?

int InterpolationSearch(int x[], int key, int n) {

   int mid, min = 0, max = n-1;

   while(x[min] < key="" &&="" x[max]=""> key) {

       mid = min + ((key-x[min])*(max-min)) / (x[max]-x[min]);

       if(x[mid] <>

          min = mid + 1;

       else if(x[mid] > key)

          max = mid - 1;

       else return mid;

   }

   if (x[min] == key) return min;

   else if(x[max] == key) return max;

   return -1; // data not found

}