Jun 8, 20214 min read

C Programming Assignment Help | Binary Search And Interpolated Search

Purpose: generate random data, store it in a file, load it, use it to compare the number

of iterations in binary search with those in interpolated search .

We want to compare the behavior of binary search and interpolated search as follows:

generate an array with N random values in the range [start_value, end_value] and store them in an array, A.
generate S random values in the range [start_value, end_value]
sort the array A
for each number, val, from the S values, search it in A using both binary search and interpolated search.

Record and print :

1. the index where val was found (-1 if not found in A)

2. how many loop iterations each method required until it finished.

print the average loop iterations over the S searches.

However when running such experiments, it is useful to be able to reproduce them at a

later time and thus we want to save the random data used in the experiment in a file.

So we break it in two parts:

1. generate the random data and save it in a file.

2. load the data from the file, run the experiments and print the results. For printing the results we want two modes:

1-verbose (prints the sorted array and information for each value that was searched and the averages over all searches. This is useful in debugging and understanding the program and data behavior)
2-not verbose (prints only the averages. This is useful when we are confident that the program is correct and we want to run it for large N and S).

Program specifications:

1. The program will repeatedly allow the user to make a menu choice: 0-exit, 1- create and save to file, 2-load from file and run binary search and interpolated search.

2. If the user selected option 1 (create and save) he will next be prompted to enter, in this order:

1. N - number of elements in an array,

2. S - number of values that will be searched in the array

3. start_value

4. end_value

5. filename - name of file where the data will be saved. It must include the file extension (e.g. data1.txt). It can have at most 100 characters.

The program will open a file filename for writing and write on the first line, separated by spaces the 4 numbers: N S start_value end_value

Next it will generate N random numbers in the range [start_value, end_value] and write them on a new line in the file. They will also be separated by spaces.

(When loaded, these will be used as the array elements.)

Next it will generate S random numbers in the range [start_value, end_value] and write them on the third line of the file. They will also be separated by spaces. (When loaded, we will search for each one of these among the array elements.)

Here is a sample of the file format:

16 10 0 100

84 29 64 74 66 53 49 41 2 60 38 23 21 47 58 3

24 48 71 8 79 5 26 44 28 43

Here is a file where the values searched are from the array: data2.txt. Load and run this file as well.

3. If the user selects option 2 (load and run) he will be asked for the file name (e.g. data1.txt) and a number (1-verbose/2-not verbose).

It will open the file with the given name and load the data.

Next it will sort the array.

For each of the S numbers on the last line, search it in the array A

Print the required information (in verbose style or not). See the sample run below.

If the file does not exist, it will print an error message.

4. The program output must match the shown behavior including: menu options (0-exit, 1-create and save, 2-load and run and 1 or 2 for verbose mode), formatting of table, not crashing for file not found, format of files,...

5. For binary search, you can use the code discussed in class. Improve the code to keep track (update) everytime the while loop runs a new iteration.

6. Implement interpolated search. This is a searching method where instead of checking the element in the middle, you check one that is proportionally away from the start as how far the search value is from the start value. For example, assume that N=100 and the numbers in the array are uniformly distributed and are in the range 0 to 1000. If you are searching for value 10, it is more likely to be among the first elements than at the middle. In your implementation, copy the binary search code and replace the calculation of the middle index with:

m = left + (value - A[left])*(right - left) / (A[right] - A[left]);

This modification will cause interpolated search to crash for some special cases. Thoroughly test your code and fix it as needed.

Refresh the slides on Examples of Algorithms. See slides at pages 47-50 for an application of interpolated search.

Sample run (from omega). Download data2.txt from this page, or create your own.

[astefan@omega hw2]$ gcc -o search search.c

[astefan@omega hw2]$ ./search

0-exit

1-create and save random data for search.