C program to Implement Interpolation Search on Array of Integers

This is a C Program to implement interpolation search on array of integers.

Problem Description

We have to create a C Program which finds the position of an element in an array of numbers using Interpolation Search Algorithm, if it is present in the array.

Expected Input and Output

1. Average case : On an average interpolation search makes a total of (log(log n)) comparisons where n is the total number of elements. For example:

If the input array has the data as {1, 2, 3, 4, 5, 6}
and the element to be searched is 6,
then the expected output will be Position 6

Average case time complexity : O(log(log n))

2. Best case : If the item to be searched is a middle element of an array, interpolation search makes just one comparison and returns the position. For example:

If the input array has the data as {2, 4, 6, 8, 10}
and the element to be searched is 6,
then the expected output will be Position 3

Best case time complexity : O(1)

Program/Source Code

Here is source code of the C Program to implement Interpolation Search on array of integers. The program is successfully compiled and tested using Codeblocks gnu/GCC compiler on Windows 10. The program output is also shown below.

Note: Join free Sanfoundry classes at Telegram or Youtube

Problem Solution

1. Interpolation search is an improved variant of binary search. To apply interpolation search the data should be in sorted and equally distributed form.
2. Interpolation search uses this formula to find out the mid position of the array “mid = bottom + (top – bottom) * ((item – a[bottom]) / (a[top] – a[bottom]))“.
3. Average Case time complexity of Interpolation Search is O(log(log n)), which proves that it is way faster than Binary and Linear Search.

```
/*
```

 * C Program for Interpolation search algorithm

```
 */
```
```
#include <stdio.h>
```
```
#define MAX 200
```
```
/* Interpolation search function */
```

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;
```
```
}
```
```
/* End of interpolation_search() */
```
```
/* The main() begins */
```
```
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;
```
```
}
```

Program Explanation

1. To apply interpolation search the data should be in sorted and equally distributed form. Either we have to insert elements in ascending order, or we can sort the array in ascending order.
2. In interpolation search we divide the array using the formula for mid and check whether the key value that is searched for is present in any of the divided parts or not.
3. On comparing the mid value of the array calculated from formula and the key value that is searched, the algorithm decides which part to start searching.
4. It continues like that and the values of top and bottom i.e. the starting index and the ending index of the array inside function definition keep on changing till we locate the element.
5. The important thing about interpolation search is that it should be applied upon a sorted and equally distributed array only.

Runtime Test Cases

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

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Implement Binary Search with Window

» Next - C Program to Generate All Possible Combinations of List of Numbers

Related Posts:

Recommended Articles: