interpolation search Algorithm

Interpolation search is an efficient algorithm for searching a specific value within a sorted array of values. This search algorithm takes advantage of the sorted nature of the array by estimating the position of the target value based on the values at the beginning and end of the array, and the relative size of the target value. The basic idea is to use the target value to calculate a likely position within the array where the value might be found, and then narrow down the search range accordingly. This approach allows the algorithm to find the target value more quickly than other search algorithms, such as linear search or binary search, especially when dealing with large arrays with uniformly distributed values. The interpolation search algorithm starts by calculating the position of the target value using a linear interpolation formula, which involves the first and last elements of the search range, and the target value itself. This position acts as a guess for the location of the target value in the array. Based on this guess, the algorithm determines whether the target value is before, after, or at the guessed position. If the target value is found, the algorithm returns the index of the target value. If the target value is before or after the guessed position, the search range is updated accordingly, and the interpolation search process is repeated within the new search range. This process continues until the target value is found, or the search range becomes empty, indicating that the target value is not in the array. As the search range narrows down with each iteration, the interpolation search algorithm converges to the target value more rapidly than linear or binary search algorithms.
#include<stdio.h>

/* By comparison, binary search always chooses the middle of the remaining
 * search space, discarding one half or the other, depending on the comparison
 * between the key found at the estimated position and the key sought. The remaining
 * search space is reduced to the part before or after the estimated position.
 * The linear search uses equality only as it compares elements one-by-one from the start, ignoring any sorting.
 * On average the interpolation search makes about log(log(n)) comparisons (if the elements
 * are uniformly distributed), where n is the number of elements to be searched. In the worst case
 * (for instance where the numerical values of the keys increase exponentially) it can make up to O(n) comparisons.
 * In interpolation-sequential search, interpolation is used to find an item near the one being searched for,
 * then linear search is used to find the exact item. */

int interpolationSearch(int arr[], int n, int key)
{
    int low = 0, high = n - 1;
    while (low <= high && key >= arr[low] && key <= arr[high]) {
        /* Calculate the nearest posible position of key */
        int pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]);
        if (key > arr[pos])
            low = pos + 1;
        else if (key < arr[pos])
            high = pos - 1;
        else /* Found */
            return pos;
    }
    /* Not found */
    return -1;
}


int main()
{
    int x;
    int arr[] =  {10, 12, 13, 16, 18, 19, 20, 21, 22, 23,
                  24, 33, 35, 42, 47};
    int n = sizeof(arr)/sizeof(arr[0]);

    printf("Array: ");
    for(int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\nEnter the number to be searched: ");
    scanf("%d",&x); /* Element to be searched */

    int index = interpolationSearch(arr, n, x);

    /* If element was found */
    if (index != -1)
        printf("Element found at position: %d\n", index);
    else
        printf("Element not found.\n");
    return 0;
}

LANGUAGE:

DARK MODE: