Algorithms and Data Structures
Exercise 10
Search (Binary Search)

Question 1 [PostScript for printring]

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.

Question 2

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]);.

Question 3

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.


Written by わかまつなおき