Exercise 3

Binary Search and Recursion

Due Date - Feburary 11, 2012 @ 12:00pm

Introduction

Within sets of ordered data, we need efficient ways to determine whether or not values exist in the set.  A popular way to perform this search is by binary search.  A binary search starts by comparing the value being searched for, aka the key, and the n/2 value of the ordered set.  The set is sorted in ascending order, which means that numbers become increasingly large. Therefore, if the key is greater then the value, the search continues on the set containing the (n/2)+1 to the n values.  If the key is less then the n/2 value, the search continues on the set containing the 1st to the (n/2)-1 values.  If the key happens to be the value that is being searched for, the algorithm terminates.

Links about recursion:

Introduction to recursion with examples.
The code is in C++. However the only difference in this code respect to C is how the print to console. "cout<<"hello"" is used instead of printf("hello").

Demonstration of a step to step recursion algorithm

Recursion vs Iteration

Assignment

      Write a recursive C program that performs a binary search on a set of numbers given in a file. 

Output Code

    You can download the code for the expected output here.  The output code contains three functions.

PrintIndex - Prints the index of the key.  If the key is not in the set, a message is printed.

PrintList - Prints current section of the list is being searched 

PrintError - Prints the appropriate error messages if you have problems opening a file or there is the wrong number of command-line inputs

Specifications

1. You should print an error message and exit the program with a value of EXIT_FAILURE if the user does not give enough command line arguments.  The expected output is in the output code (error code 1).
2. You should print an error message and exit the program with a value of EXIT_FAILURE if the user gives an invalid file.  The expected output is in the output code (error code 2).
3. You should print an error message and exit the program with a value of EXIT_FAILURE if the dynamic memory is not allocated properly.  The expected output is in the output code (error code 3).
4. The key and the name of file contain the ordered set will be given as a command-line arguments.
5. You can assume the values in the set to be integers, one for each line in the input text file. (Hint: use strtol() to convert from strings to integers.)
6. Your binary search algorithm must be implemented as a recursive function.
7. There is no maximum number of values in a set.
8. You will need to dynamically allocate memory to store the ordered set.
9. The set of number may or may not be ordered.  If they are not ordered, you should print an error message and exit the program with a value of EXIT_FAILURE.  The error message is given in the output code (error code 4).  
10. Only one instance of a value will be in a set. (Each value in the set is unique).
11. You should print out the current part of the set that you are searching.
12. Your algorithm should detect if the key to search for does not exist in the set (this should be passed as index -1 to the PrintIndex output code).
13. The largest number possible in the set is 1000000

Warning

You cannot use anything like the following:

    int count = 0;
    ... /* find the number of elements */
    int array[count]; 

You have to use malloc and free.

Compile and Execute

You will need to create a Makefile to compile your code.  You can find an introduction on Makefiles here.  You should use "gcc -Wall" instead of "gcc".  This will turn on warning messages.  Treat warning messages seriously because warnings are very likely errors.

Warning messages are often indications of errors. For this assignment, you lose 0.1 point for each warning message. The command will generate an executable file called "ex3."

To execute this program, type

./ex3 <key> <filename>

The second argument (argv[1]) is the key to search for and the third argument (argv[2]) is the file containing the set

Testcases

You can find a suite of testcases here.  You can find which key was being search for in the solution file.  

Submission Procedure

   Create a zip file contain the folowing files

• At least 1 .c and 1 .h file
• Makefile - The makefile should produced the executable "ex3".

   and then submit to the course grading website. 

You need to provide a user name and a password through Blackboard before submission.  The user name and the password are different from your Purdue career account.

.h Files

A .h file, short for header file,  typically contains the following

• All the the C library files that your program will need (i.e. stdio.h, stdlib.h, etc.)
• All constants you will need.  Constants can be defined using the #define command.  An example would be  "#define MAXLEN 102".
• All function headers  for the function in your program. 

Once completed, your .h file should be included in your .c file.  This is done by typing the following: #include "filename.h"

Memory Management

Memory management (allocation and release) is an important part of ECE 264. You have to allocate enough memory to make your program work. You have to allocate and release memory as needed. You are not allowed to allocate a large piece of memory regardless of the input size. We will restrict stack size to prevent that. You will receve heavy penalty (50%) if your program does not release all memory (i.e. memory leak). We will use valgrind to check for memory leaks.

Grading

The maximum score for this exercise is 2.0 points.

Examples

If the key is 25 and the ordered set is the following

{12, 17, 25, 29, 346, 435, 4257, 584678}

Your program should output

 

If the key is 500 and the ordered set is the following

{1, 4, 8, 23, 43, 7890, 45654, 7589057, 8900000}

Your program should output

Hint

If you read the file using fgets, consider to use strtol to convert a string to an integer. Check this page about how to use strotol.

You can also use fscanf to read an integer from a file.