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 NEXT LAB)

• 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.
• Make sure you wrote a RECURSIVE function.
• 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).
• 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!


---

Grading Scheme

Program compile and execute 20%
Program meets all specifications 70% (e.g. makefile, recursion, proto.h, etc. Also ask your TA specifically about what preciously he is looking for)
Program follow code conventions and contain proper documentation. 10%