Assignment 7 Solutions

CSCI 132 Data Structures--Spring 2014

Assignment 7 Solutions
Solution ternary() code:
/*******************************************************************
 * Name: Brenda Student
 * Date: 4/13/14
 * Course: CSCI 132 Section 01
 * Assignment: Homework 7
 * Instructor: Royden
 * Program: search_compare.cc
 * Purpose: Program to count the number of comparisons made in 
 * different search algorithms: Sequential, binary search 1 and ternary
 ***************************************************************************/

// Only the ternary and run_ternary functions are shown here.

Error_code run_ternary(const List &the_list,
              const Key &target, int &position)
/*
Post: If an entry in the_list has key equal to target, then return
success and the output parameter position locates such an entry
within the list.
Otherwise return not_present and position becomes invalid.
*/
{
  return ternary(the_list, target, 0, the_list.size() -1, position);
}

Error_code ternary(const List &the_list, const Key &target, 
              int bottom, int top, int &position)
  /* Pre: The indices bottom to top define the range in the list to search 
  for the target.
  Post: If a Record in the range of locations from bottom to top in the_list 
  has key equal to target, then position locates one such entry and a code of
  success is returned. Otherwise, the Error_code of not_present is returned
  and position becomes undefined.*/
{
  Record data;
  if (bottom <= top) {
    int oneThird = bottom + (top - bottom)/3;
    the_list.retrieve(oneThird, data);
    if (data == target) {
      position =  oneThird;
      return success;
    } else if (data > target) {
      return ternary(the_list, target, bottom, oneThird-1, position);
    } else {
      int twoThirds = bottom + (2*(top - bottom))/3;
      the_list.retrieve(twoThirds, data);
      if (data == target) {
	    position = twoThirds;
	    return success;
      } else if (data > target) {
	    return ternary(the_list, target, oneThird+1, twoThirds-1, position);
      } else {
	    return ternary(the_list, target, twoThirds+1, top, position);
      }
    }
  } else {
    return not_present;
  }
}