Interpolation Search In C

When a specific element exists within an array, it is essential to develop a C program that employs the Interpolation Search Algorithm to ascertain its precise location within the integer array.

Cases of Interpolation Search:

There are multiple instances of Interpolation Search. These scenarios include:

1. Average Case:

Interpolation search algorithms typically require (log(log n)) comparisons to locate an element, with n representing the total quantity of elements in the collection.

Example:

The expected outcome will be Index 5 when the input array consists of the provided elements: 1, 2, 3, 4, 5, 6, and the target element is element 6.

The time complexity in the average scenario is O(log(log n)).

2. Best Case:

Interpolation search involves a single comparison to determine and return the position in case the target object is situated as the middle element within an array.

Example:

The output will be the 3rd position if the array input consists of the values "2, 4, 6, 8, 10," and the target element is "6". The best-case time complexity is O(1).

Example Code:

Here is the code snippet for a C program that employs an integer array to execute interpolation search. The program has been compiled and tested effectively using the GCC compiler. Additionally, the program output is displayed below.

Dispute Resolution

• ✅ Binary search has been improved by interpolation search . Data must be sorted and evenly distributed to use interpolation search .
• ✅ The mid position of the array is determined by the interpolation search using the formula "mid = bottom + (top - bottom) * ((item - a[bottom]) / (a[top] - a[bottom]))" .
• ✅ S tandard Interpolation Search has an Average Case case time complexity of O(log(log n)) , which demonstrates that it is much faster than Binary and Linear Search .

Code:

//C program for the algorithm of interpolation
#include <stdio.h>
#define MAX 200

int interpolation_search(int a[], int bottom, int top, int item)
{
    int mid;
    while (bottom <= top) {
        mid = bottom + (top - bottom)*((item-a[bottom])/(a[top]-a[bottom]));
        if (item == a[mid])
            return mid + 1;
        if (item < a[mid])
            top = mid - 1;
        else
            bottom = mid + 1;
    }
    return -1;
}

int main()
{
    int arr[MAX];
    int i, num;
    int item, pos;
    printf("\nEnter total elements (num < %d) :", MAX);
    scanf("%d", &num);
    printf("Enter %d Elements in ascending order:\n",num);
    for (i = 0; i < num; i++)
        scanf("%d", &arr[i]);
    printf("\nSearch For : ");
    scanf("%d", &item);
    pos = interpolation_search(&arr[0], 0, num - 1, item);
    if (pos == -1)
        printf("\nElement %d not found\n", item);
    else
        printf("\nElement %d found at position %d\n", item, pos);
    return 0;
}

Output:

Test case 1:

Enter total elements (num < 200) :5
Enter 5 Elements in ascending order:
1
2
3
4
5
Search For : 4
Element 4 found at position 4

Test case 2:

Enter total elements (num < 200) :6
Enter 5 Elements in ascending order:
1
2
3
4
5
6
Search For: 2
Element 2 found at position 2

Program Description

• ✅ The data must be sorted and evenly distributed before using interpolation search . Either we sort the array in ascending order , or we must insert elements into the array in ascending order .
• ✅ If we want to do an interpolation search , we divide an array using the mid formula and determine whether the sought-after key value is present in any of the divided portions or not.
• ✅ The algorithm chooses the area to search for by comparing the mid value of the array determined by the formula with the key value that is searched.
• ✅ This process continues, and the top and bottom , or the starting index and ending index of the array inside the definition of the function, keep shifting until we find the element.
• ✅ The crucial aspect of interpolation search is that it should only be used with an equally dispersed and sorted array .