Section 1 - Linear Searching

2B.1.1 Searching for a Student

We introduce an example of the Student class in which we have an array of Student objects.  A Student will consist of two fields, a name, and a total score.  We will not complicate the example by using both a first and last name since the principles are unchanged using this simpler version.  The Student class will have static class method, arraySearch() that takes three parameters:

1. A Student array to search.
2. A last name (a string) for which to search (called the search key).
3. The size (length) of the array to be searched.

If arraySearch() finds a student in the array that matches the search key, it returns the index of that Student, i.e., the array index where the Student was found.  If not, it returns -1.  Here is how arraySearch() can be used:

string last;
int found;

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

Why is arraySearch() going to be a static method and not an instance method?  Remember the reason we gave for declaring a method static?  This is a perfect opportunity. It operates on class data, yet there is no single object that would naturally be used to call it.

This static class method is very easy to write. We just plow through the array, comparing the last names until we find a match.  Here it is:

int Student::arraySearch(Student array[], string keyLast,
int arraySize)
{
  for (int k = 0; k < arraySize; k++)
    if ( array[k].lastName == keyLast )
      return k;  // found match, return index

  return -1;   // fell through - no match
}

There isn't much fancy going on here.  This is called a linear search because we are going through the array in a straight line from bottom to top, until we find a match.

Finally, here is the whole program with an output, demonstrating the linear search.  This is a good review for how classes are defined and used for any of you who need extra review on this topic from CS 2A.  Read and understand this example.

#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 int arraySearch(Student array[],string keyLast,int arraySize);
  string toString();
};  // 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)
  };
  string last;
  int found;

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

  Student::printArray("Array to be searched: ", myClass, arraySize);

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

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

  last = "cassar";
  found = Student::arraySearch(myClass, last, arraySize);
  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 the string as 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::arraySearch(Student array[], string keyLast,
int arraySize)
{
  for (int k = 0; k < arraySize; k++)
    if ( array[k].lastName == keyLast )
      return k;  // found match, return index

  return -1;   // fell through - no match
}

// end of Student method definitions  --------------

The output:

Searching is an algorithm.  The longer the list of students, the longer this algorithm, i.e., the search, takes to complete.  In CS 2C or any data structures course, you will learn to analyze algorithm running times and devise various ways to vastly improve performance.  Very shortly in this course, we will see a technique for improving the above search algorithm to have a faster running time.