C Exercises: Find the position of a target value within a array using Interpolation search

C Programming Searching and Sorting Algorithm: Exercise-2 with Solution

Write a C program to find the position of a target value within an array using interpolation search.

From Wikipedia:
Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values). It was first described by W. W. Peterson in 1957. Interpolation search resembles the method by which people search a telephone directory for a name (the key value by which the book's entries are ordered): in each step the algorithm calculates where in the remaining search space the sought item might be, based on the key values at the bounds of the search space and the value of the sought key, usually via a linear interpolation. The key value actually found at this estimated position is then compared to the key value being sought. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or after the estimated position. This method will only work if calculations on the size of differences between key values are sensible.

Sample Solution:

Sample C Code:

#include <stdio.h>
// Function to perform interpolation search in a sorted array
int interpolation_Search(int array_nums[], int array_size, int n)
{
    // Initialize the lower and higher positions for the search
    int lower_pos = 0, higher_pos = array_size - 1;
    // Perform interpolation search while the search space is valid
    while (lower_pos <= higher_pos && n >= array_nums[lower_pos] && n <= array_nums[higher_pos])
    {
        // Calculate the position using interpolation formula
        int n_pos = lower_pos + ((n - array_nums[lower_pos]) * (higher_pos - lower_pos)) / (array_nums[higher_pos] - array_nums[lower_pos]);
        // If the element is greater, update the lower position
        if (n > array_nums[n_pos])
            lower_pos = n_pos + 1;
        // If the element is smaller, update the higher position
        else if (n < array_nums[n_pos])
            higher_pos = n_pos - 1;
        // If the element is found, return its position
        else  
            return n_pos;
    }
    // If the element is not found, return -1
    return -1;
}
// Main function
int main()
{
    int n;
    // Sorted array for interpolation search
    int array_nums[] = {0, 10, 20, 20, 30, 50, 70, 75, 82, 92, 115, 123, 141, 153, 160, 170};
    int array_size = sizeof(array_nums) / sizeof(array_nums[0]);
    // Print the original array
    printf("Original Array: ");
    for (int i = 0; i < array_size; i++) 
        printf("%d ", array_nums[i]);   
    printf("\n");
    // Input a number to search
    printf("Input a number to search: ");
    scanf("%d", &n); 
    // Perform interpolation search and print the result
    int index = interpolation_Search(array_nums, array_size, n);
    if (index != -1)
        printf("\nElement found at position: %d", index);
    else
        printf("\nElement not found..!");
    // Return 0 to indicate successful execution
    return 0;
}

Sample Output:

Original Array: 0 10 20 20 30 50 70 75 82 92 115 123 141 153 160 170
Input a number to search: 82

Element found at position: 8
--------------------------------
Process exited after 3.503 seconds with return value 0
Press any key to continue . . .

Flowchart:

C Programming Code Editor:

Previous: Write a C program to find the position of a target value within a sorted array using Binary search.
Next: Write a C program to find the position of a target value within a sorted array using Jump search.