interpolation_search.c
searching Implementation
46 lines1339 bytesC
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