-
Notifications
You must be signed in to change notification settings - Fork 0
/
interpolation-search.c
55 lines (42 loc) · 1.08 KB
/
interpolation-search.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#define MAX 8
//the list should be in sorted form otherwise result will be wrong
int list[MAX] = {1,5,10,11,32,55,68,85};
int find(int no)
{
int low = 0;
int high = MAX-1;
int mid = -1;
int index = -1;
int comparisions = 1;
while(low <= high)
{
comparisions++;
/* To understand interpolation formula visit:
https://study.com/academy/lesson/interpolation-in-statistics-definition-formula-example.html
*/
mid = low + (((high - low) / (list[high] - list[low])) * (no - list[low]));
if(list[mid] == no)
{
index = mid;
printf("Total Comparisions: %d \n",comparisions);
break;
}
else
{
if(list[mid] < no)
low = mid + 1;
else
high = mid - 1;
}
}
return index;
}
int main(){
int index = find(32);
if(index != -1)
printf("Value found at location: %d",(index+1));
else
printf("Value was not found");
return 0;
}