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:

• A data object of searching must be displayed.
• Input each key for binary search and interpolation search, and display the result.

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.

int a[N]={ 1, 4, 6, 9, 10, 13, 19, 23, 25, 30 };

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:

• Number of a data is 100000 and data is constructed by random numbers.
• Sort data by the sort functions which you have written in exercise 8 or 9.
• Display data by each 30th because the data amount is too large.

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