Consider the following sorted data.
1 4 6 9 10 13 19 23 25 30
(1) Write a process of searchin 9
in this data by binary search.
(2) Write a process of searchin 9
in this data by interpolation search.
Write a program that searches by binary search and interpolation search. The program must fulfill the following conditions:
Example for executing: % ./a.out data: 1 4 6 9 10 13 19 23 25 30 Input key for binary search: 9 found. Input key for interpolation search: 9 found. % ./a.out data: 1 4 6 9 10 13 19 23 25 30 Input key for binary search: 8 not found. Input key for interpolation search: 8 not found.
You may initialize the sorted data when it is declared.
int a[N]={ 1, 4, 6, 9, 10, 13, 19, 23, 25, 30 };
You can create an interpolation function by changin x=(l+r)/2;
of binary search to x=l+(v-a[l])*(r-l)/(a[r]-a[l]);
.
Write a program that calculates the comparison time both for binary search and interpolation search, and display them. The program must fulfill the following conditions:
Additionally, fix interpolation function in question 2, because it have bugs which some data make it to be infinity loop or segmentation fault.
Example for excuting: % ./a.out data: 9 10 16 20 20 25 31 40 41 47 50 60 63 65 67 67 73 77 78 83 84 84 86 87 91 92 99 Input key for binary search: 99 found. Number of Comparison: 10 Input key for interpolation search: 99 found. Number of Comparison: 2
The interpolation function in question 2 does not consider the case of division by 0 and the case when x equals a negative number.