CSCI 112
Lab 9 - Recursive Binary Search

Objectives:

Generate a RECURSIVE binary search function.
Demonstrate it on a sorted array of letters.
Learn about using Dynamic Memory Allocation.

Readings:

Review the description of binary search – Programming Project 12 on pages 449-450 in the 7th edition, page 443 in the 6th edition, or pages 428-429 in the 5th edition of Hanly/Koffman text.
Read Chapter on Recursion in the textbook (i.e. chapter 9 in the 7th edition, or chapter 10 in the 6th or 5th edition).

Deliverables: (DUE BY MIDNIGHT ON 04/09/2013)

Submittal of the following files:

Makefile
Proto.h
Lab9.c
BinarySearch.c

TO DO (for this lab)

Design and Write a program to solve Programming Project #6 (with a slight modification!) on page 564 in the 7th edition of the Hanly/Koffman text (or on page563 in the 6th edition, or page 549 in the 5th edition).
For the modification - we will use letters for input instead of integers.
Be sure your Makefile will properly rebuild the run image.
Make sure to dynamically allocate (use calloc(), or malloc() functions from stdlib.h) and free memory as needed.
Inputs: a data file redirected with:

the number of letters in the array
a sorted list of letters
the number of letters to search for
a list of letters to search for.

Example of input file follows:

6
a d n o x y
3
n x z

Outputs: For each search, print out (1) the letter that you were asked to search for, (2) the index of the location (we count starting from 0!), where the letter has been found or an error, and (3) the level of binary search tree where the letter has been found (the level reflects the number of recursive calls that were needed to find the letter using binary search function). Example follows:

  n found at    2 during iteration    0.
  x found at    4 during iteration    1.
  z not found!
Note, the above output with blanks marked (b) would look like:
bbbn found at bbb2 during iteration bbb0.
bbbx found at bbb4 during iteration bbb1.
bbbz not found!

Hints on implementing your algorithm:

Make sure that you wrote a RECURSIVE function for searching.
You may want to use global variable to count iterations of your search (i.e. levels of your binary tree). Start counting from 0 (i.e. root of the tree represents level 0).

LAB 9 ENRICHMENT