CS201
Lab 9 - Recursive Binary Search

Objectives:

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

Readings:

Review the description of binary search (Programming Project 12 in Chapter 8, pages 428-429).
Read Chapter 10 in the Hanly/Koffman text.

Deliverables: (DUE BY THE BEGINNING OF YOUR LAB IN 2 WEEKS)

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 on page 549 of the Hanly/Koffman text.
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 values in the array
a sorted list of integers
the number of values to search for
a list of integers to search for.

Example of input file follows:

6
1 5 8 19 21 32
3
8 21 44

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

   8 found at    2 during iteration    0.
  21 found at    4 during iteration    1.
  44 not found!
Note, the above output with blanks marked (b) would look like:
bbb8 found at bbb2 during iteration bbb0.
bb21 found at bbb4 during iteration bbb1.
bb44 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