Section 5 - Complete Binary Search Program

2B.5.1 Student Search in Binary Form

Here is the complete listing, using the updated Student class that contains only one name.  We have discussed every detail of this example somewhere before, but that doesn't mean you should not study it carefully line-by-line.  It contains a mega-dose of Vitamin C++ which will make you strong, rich and famous.  Run it.  Modify it, and rerun it.  Study it.  Make it your own.

#include <string>
#include <iostream>
#include <sstream>
using namespace std;

// class Student prototype -----------------------
class Student
{
private:
  string lastName;
  long totalPoints;

public:
  Student( string lst, long pts);
  static void printArray(string title, Student data[],
  int arraySize);
  static void arraySort(Student array[], int arraySize);
  static int binarySearch(Student array[], string keyLast,
  int firstIndex, int lastIndex);
  string toString();

private:
  static bool floatLargestToTop(Student data[], int top);
  static void swap(Student &a, Student &b);
};  // end of class Student prototype --------------

int main()
{
  Student  myClass[] = {
    Student("smith", 95),
    Student("bauer", 123),
    Student("jacobs", 195),
    Student("renquist", 148),
    Student("3ackson", 108),
    Student("perry", 225),
    Student("loceff", 44),
    Student("stollings", 452),
    Student("charters", 295),
    Student("cassar", 321)
  };

  int arraySize = sizeof(myClass) / sizeof(myClass[0]);

  Student::printArray("Array (unsorted) to be searched: ",
  myClass, arraySize);
  Student::arraySort(myClass, arraySize);
  Student::printArray("Array (sorted) to be Searched:",
  myClass, arraySize);

  string last;
  int found;

  last = "stollings";
  found = Student::binarySearch(myClass, last, 0, arraySize - 1);
  if ( found >= 0 )
    cout << last + " IS in list at position " << found;
  else
    cout << last + " is NOT in list.";
  cout << endl;

  last = "Jacobs";
  found = Student::binarySearch(myClass, last, 0, arraySize - 1);
  if ( found >= 0 )
    cout << last + " IS in list at position " << found;
  else
    cout << last + " is NOT in list.";
  cout << endl;

  last = "cassar";
  found = Student::binarySearch(myClass, last,
  0, arraySize - 1);
  if ( found >= 0 )
    cout << last + " IS in list at position " << found;
  else
    cout << last + " is NOT in list.";
    cout << endl << endl;
}

// begining of Student method definitions -------------

// constructor requires parameters - no default supplied
Student::Student( string lst, long pts)
{
  lastName = "zz-error";
  totalPoints = 0;
  // at least require that it starts with a letter
  if (lst.length() > 0 && isalpha(lst[0]))
    lastName = lst;
  if (pts >= 0 && pts <= 1000)
    totalPoints = pts;
}
// return a string containing both name and score to client
string Student::toString()
{
  // we need to convert score to string:
  string strPoints;
  ostringstream cnvrt;
  cnvrt << totalPoints;
  strPoints = cnvrt.str();

  string strStudent = lastName + " Points: " + strPoints;
  return strStudent;
}

// print out array with string as a title for the message box
void Student::printArray(string title, Student data[], int arraySize)
{
  cout << title << endl;
  for (int k = 0; k < arraySize; k++)
  cout << data[k].toString() << endl;
  cout << endl;
  cout << endl;
}

int Student::binarySearch(Student array[], string keyLast,
int firstIndex, int lastIndex)
{
  int middleIndex, result;

  if (firstIndex > lastIndex)
    return -1;
  middleIndex = (firstIndex + lastIndex) / 2;
  result = keyLast.compare(array[middleIndex].lastName);

  if (result==0)
    return middleIndex;   //found him!
  else if (result < 0)
    return binarySearch(array, keyLast, firstIndex, middleIndex-1);
  else
    return binarySearch(array, keyLast, middleIndex+1, lastIndex);
}

void Student::arraySort(Student array[], int arraySize)
{
  for (int k = 0; k < arraySize; k++)
    if (!floatLargestToTop(array, arraySize-1-k))
      return;
}

// returns true if a modification was made to the array
bool Student::floatLargestToTop(Student data[], int top)
{
  bool changed = false;

  // notice we stop at length -2 because of expr. k+1 in loop
  for (int k =0; k < top; k++)
    if (data[k].lastName.compare(data[k+1].lastName) > 0)
    {
      swap(data[k], data[k+1]);
      changed = true;
    }
  return changed;
}

void Student::swap(Student &a, Student &b)
{
  Student temp("", 0);

  temp = a;
  a = b;
  b = temp;
}
// end of Student method definitions  --------------

The output: