CS201
Lab 10 - Recursive Binary Search

Objectives:

• Generate a RECURSIVE binary search function.
• Demonstrate it on a sorted array of integers.

Readings:

• Read Chapter 10 in the Hanly/Koffman text.

Deliverables: (DUE BY THE END OF YOUR LAB ON 4/4 & 4/5!)

• Submittal of the following files:
  • Makefile
  • Proto.h
  • Lab10.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.
• 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!


Helpful Hints

Make sure you wrote a RECURSIVE function.

Dynamically allocate and free memory as needed.

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 the tree represents level 0). Look at this lecture for additional example.