Search an array of integers for a VAL value entered on the keyboard. Display the position of VAL if it is in the array, otherwise display a corresponding message. The INDEX value that is used to memorize the position of the value in the array, will have the value -1 as long as VAL was not found.

Condition: Table A must be sorted and elements are uniformly distributed.

The interpolation search is different from the binary search as it tunes the search process according to the value of the key being searched. For example, if the value of the element is closer to the last element, the interpolation search will start searching toward the end side.

Method:

• Step 1: Iteratively, calculate the value of the position using the following formula
  \(position = lower + (\frac{upper - lower}{A[upper] - A[lower]}) \times (val - A[lower])\)
  This formula return higher value of position for VAL closer to A[upper], and smaller value when VAL is closer to A[lower]
• Step 2: If it is a match, exit the loop.
• Step 3: If VAL is less than A[position], calculate the probe position of the left sub-array. Otherwise calculate the same in the right sub-array.
• Step 4: Repeat until a match is found or the sub-array reduces to one element.

#include<stdio.h>
#include<conio.h>
#define SIZE 50
void main()
{
	int A[SIZE], N, val;
	int i;
	int lower, upper;
	int found, position;

	do {
		printf("Enter the dimension: ");
		scanf("%d", &N);
	} while (N <= 0 || N > SIZE);


	// reading the array in ascending order
	printf("Enter A[0]: ");
	scanf("%d", &A[0]);
	for (i = 1; i < N; i++)
	{
		do{
			printf("Enter A[%d]: ", i);
			scanf("%d", &A[i]);
		}while(A[i]<A[i-1]);
	}

	printf("Enter the element to find: ");
	scanf("%d", &val);


 	/* Display the array */
 	printf("Given array : \n");
 	for (i=0; i<N; i++)
    		printf("A[%d]=%d\n",i, A[i]);
 	printf("\n");


 	/* Initializing the boundaries of the search domain */
 	lower=0;
 	upper=N-1; // at the first i consider searching the entire array
 	/* finding the index of the val */
	found=0;
 	while ( lower<=upper  && val >= A[lower] && val <= A[upper] && !found)
        {
		if(lower==upper) // we reached a sub-array of one element
		{
			if(A[lower]==val)
			{
				found=1;
				position=lower;
			}
		}
		else
		{
			// get a new position depending on the array values
			position = lower + (((1.0*upper - lower) / (A[upper] - A[lower])) * (val - A[lower])); 
         		
        		if (A[position] == val) 
            			found=1; 
        		else
				if (A[position] < val) 
            				lower = position + 1; 
 				else
            				upper = position - 1; 
		}
        }


 	if (!found)
     		printf("%d not found in the array.\n", val);
  	else
     		printf("%d is found at index %d.\n", val, position);

	getch();
}