Exercise 4

Binary Search Using Recursion

Due Date - September 25, 2012 @ 6:00pm

Introduction

Within a set of ordered data, we need efficient ways to determine whether or not a value exists in the set. The set is sorted in ascending order, which means that numbers become increasingly larger. A popular way to perform this search is binary search.  A binary search starts by comparing the value being searched for, called the key, and the middle value of the ordered set.   If the key is greater then the value, the search continues on the set containing the second half of the set.  If the key is less then the middle value, the search continues on the first half of the set.  If the key happens to be the value that is being searched for, the algorithm terminates. If the key is not found and no more value is left for comparison, the key does not exist in the set.

Assignment

      Write a C program that applies the method of recursion to perform binary search.

Specification

1. Your program should exit and print an error message by using the code given in PrintError() under the following circumstances:

• If the user does not give enough arguments.
• If the program can’t open the file.
• If the dynamic memory is not allocated properly.
• If the numbers in the file are not sorted in increasing order.

2. The value of the key and the name of the file are given as a command-line arguments. (e.g. ./ex3  <filename>  <key>)
3. Your binary search algorithm must be implemented as a RECURSIVE function.
4. You will need to dynamically allocate memory to store the ordered numbers.
5. You can assume the values in the file are distinct.
6. Your program should detect if the "key" exists in the file or not.  If it's not int the file, print message by using PrintIndex(ind, key) and set ind=-1.  If the key exists in the file, print the key's location by using PrintIndex(ind,key).  Note: index 0 refers to the first number in the file.

7. You cannot use anything like the following:

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

   You have to use malloc and free. Failure to do so wil result in loss of points.

8. The numbers in the file can be stored in a 4-byte integer ("int" in C). You don't need to test extreme cases whether the numbers in the file may need more than 4 bytes.

9. Your output needs to show how many numbers in the file and how many times you use recursion. 

10. You should check memory leak. Failure in the valgrind check wil result in loss of 50% points for each testcase.

Skeleton

You can download the skeleton for ex4 here.  It contains the following file

• ex4.c - Contains the main function for this assignment
• binaryseach.c - Contains the auxillary functions for this assignment
• utility.h - Contains all function headers and constants
• Makefile - Contains sections that will compile, run some of the provided testcases, and compare your solution with the expected solution.  To run the part that will run your code with the provided testcases and do the comparison, type make test.

Do not modify the main function (do not modify the arguments and do not modify the function body). Do not modift the PrintError function. Do not add new files and remove files. Do not modify the names, return types, and arguments of the functions in the skeleton.

You can add new functions inside binarysearch.c.

For this exercise, you should change only binarysearch.c.

For more testcases, you can download here. In the zip file, there're testcases and a script to run these testcases. You can put the unzipped files on the same directory as the excutable ./ex4 you generated and copy the script to test. The output results will store in the directory "output", and compare with the solutions in "testcase_more".

Example

  Numbers in the file:

  196 204 426 1280 5142 25719 154328 1080307 8642466

a)    Key: 204

Output:

There are 9 numbers in the file.

Binary Search: 1 times for range 0 to 8.

Binary Search: 2 times for range 0 to 3.

The value 204 is located at index 1

b)    Key: 100000

Output:

There are 9 numbers in the file.

Binary Search: 1 times for range 0 to 8.

Binary Search: 2 times for range 5 to 8.

Binary Search: 3 times for range 5 to 5.

Binary Search: 4 times for range 6 to 5.

100000 is not in the array.

Grading

2 points total.

Points will be take off if the program doesn't meet the specifcations.

You should consider possible testcases on your own. Passing all the testcases we gave you doesn't guarantee receiving  full percentage of the score.

Valgrind Check

Valgrind is used to check if your program has a memeroy leak (By Wikipedia).

In the Makefile, we have turn on valgrind check by the command:

 valgrind --leak-check=yes --verbose

In this case,-- verbose is one of the option telling valgrind to give extra information on various aspects of your program, such as: the shared objects loaded, the suppressions used, the progress of the instrumentation and execution engines, and warnings about unusual behaviour.

You can refer to more options about valgrind here (Provided by Valgrind™ Developers).

While your program ends with  all the heap memeory freed, you should see the following sentences at the end of its report,

==6104== HEAP SUMMARY:
==6104==     in use at exit: 0 bytes in 0 blocks
==6104==   total heap usage: 2 allocs, 2 frees, 968 bytes allocated
==6104==
==6104== All heap blocks were freed -- no leaks are possible
==6104==
==6104== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 6)

The most important part of the valgrind output is the statement All heap blocks were freed -- no leaks are possible. 

If you see that statement, valgrind passed.  If not, then there is memory leak.

Submission Procedure

   Create a zip file that contains the folowing files

• ex4.c
• binarysearch.c
• utilith.h
• Makefile - The makefile should produce an executable "ex4".

To create a zip file in the Linux terminal, type

zip ex4.zip ex4.c binarysearch.c utility.h Makefile

and the submit the zip file (i.e. ex4.zip) to Blackboard

You can also submit this .zip file to the course testing website for additional testcases.

References

.h Files

• 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. 
• Any macros you have created

Your .h file should be included in your .c file. 

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