interpolation_search.c

searching Implementation

46 lines
1339 bytes
C
1#include <stdio.h>
2
3// Function to perform Interpolation Search
4// Returns index of x if it is present in arr[0..n-1], else -1
5int interpolationSearch(int arr[], int n, int x) {
6    int lo = 0, hi = (n - 1);
7
8    // Since array is sorted, an element present in array must be in range defined by corner
9    while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
10        if (lo == hi) {
11            if (arr[lo] == x) return lo;
12            return -1;
13        }
14
15        // Probing the position with keeping uniform distribution in mind
16        int pos = lo + (((double)(hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));
17
18        // Condition of target found
19        if (arr[pos] == x)
20            return pos;
21
22        // If x is larger, x is in upper part
23        if (arr[pos] < x)
24            lo = pos + 1;
25        // If x is smaller, x is in the lower part
26        else
27            hi = pos - 1;
28    }
29    return -1;
30}
31
32int main() {
33    // Array of items on which search will be conducted.
34    int arr[] = { 10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47 };
35    int n = sizeof(arr) / sizeof(arr[0]);
36
37    int x = 18; // Element to be searched
38    int index = interpolationSearch(arr, n, x);
39
40    if (index != -1)
41        printf("Element found at index %d\n", index);
42    else
43        printf("Element not found\n");
44    return 0;
45}
46