Programming Challenge 8.8 - Search Benchmarks

Example file: searchNumbers.txt

/* Search Benchmarks - This program has an array of at least 20 integers.
   It calls a function that uses the linear search algorithm to locate
   one of the values. The function keeps a count of the number of
   comparisons it makes until it finds the value. The program then calls
   a function that uses the binary search algorithm to locate the same
   value. It also keeps count of the number of comparisons to make. These
   values are displayed on the screen. */

#include "Utility.h"

int getNumbers(int[], int);
int linearSearch(const int[], int, int);
void sortNumbers(int[], int);
int binarySearch(const int[], const int, const int);
void displaySorted(const int[], const int);
void displayComparison(const int, const int, const int);

int main()
{
   const int NUMELS = 100;
  
   int userNum = 0,
       numCyclesLinear = 0,
       numCyclesBinary = 0,
       returnCode = 0;

   char again = ' ';

   /* Array holding the numbers */
   int numbers[NUMELS] = { };

   /* Gets the numbers stored in "numbers.txt" */
   returnCode = getNumbers(numbers, NUMELS);

   if (returnCode == 0)
   {
      /* Performs a selection sort on numbers */
      sortNumbers(numbers, NUMELS);

      /* Displays the sorted list of numbers */
      displaySorted(numbers, NUMELS);

      do
      {
         cout << "\n\tEnter a number to search for: ";
         cin >> userNum;

         /* Performs a selection sort on numbers */
         sortNumbers(numbers, NUMELS);

         /* Gets the result of the linear and binary search */
         numCyclesLinear = linearSearch(numbers, userNum, NUMELS);
         numCyclesBinary = binarySearch(numbers, userNum, NUMELS);

         /* Displays a comparison between the search algorithms */
         displayComparison(userNum, numCyclesLinear, numCyclesBinary);

         cout << "\n\tDo you wish to try again (y/Y) ? ";
         cin >> again;
      } while (!(again == 'N' || again == 'n'));
   }

   pauseSystem();
   return 0;
}

/* **********************************************************
   Definition: getNumbers

   This function accepts numbers and NUMELS containing the
   number of elements in the array as arguments. It reads in
   a list of numbers from "numbers.txt" and stores the values
   in the array.
   ********************************************************** */

int getNumbers(int numbers[], int NUMELS)
{
   ifstream readNums;

   int count = 0;

   readNums.open("numbers.txt");

   if (readNums)
   {
      while (count < NUMELS && !readNums.eof())
      {
         readNums >> numbers[count];
         count++;
      }     
   }
   else
   {
      cout << "\nFile open error: The file 'numbers.txt' could not\n"
           << "be opened or processed. Please make sure that the filename is\n"
           << "correct and the file is not damaged or has been moved from the\n"
           << "program folder. Please close this program now and try again ...\n\n";

      return 1;
   }

   readNums.close();

   return 0;
}

/* **********************************************************
   Definition: linearSearch

   This function accepts numbers and NUMELS containing the
   number of elements in the array as arguments. It performs
   a linear search and keeps track of the number of cycles
   performed to find the value being searched for. If the
   number could not be found, a message is displayed.
   ********************************************************** */

int linearSearch(const int numbers[], int userNum, int NUMELS)
{
   int index = 0,
       numCycles = 0;

   bool numFound = false;

   for (index = 0; index < NUMELS && !numFound; index++)
   {
      if (userNum == numbers[index])
      {
         numFound = true;
      }

      numCycles += 1;
   }

   if (numFound == false)
   {
      cout << "\n\tLinear Search:\n";
      cout << "\n\tThe number " << userNum << " has not been found ...\n"
           << "\tNumber of search cycles: " << numCycles << "\n";
   }

   return numCycles;
}

/* **********************************************************
   Definition: sortNumbers

   This function accepts numbers and NUMELS containing the
   number of elements in the array as arguments. It performs
   an selection sort on numbers in ascending order.
   ********************************************************** */

void sortNumbers(int numbers[], int NUMELS)
{
      int startScan = 0,
          minIndex = 0,
          minValue = 0,
          index = 0;

   for (startScan = 0; startScan < (NUMELS - 1); startScan++)
   {
      minIndex = startScan;
      minValue = numbers[startScan];

      for (index = startScan + 1; index < NUMELS; index++)
      {
         if (numbers[index] < minValue)
         {
            minValue = numbers[index];
            minIndex = index;
         }
      }

      numbers[minIndex] = numbers[startScan];
      numbers[startScan] = minValue;
   }
}

void displaySorted(const int numbers[], int NUMELS)
{
   cout << "\n\t\t\t\t\tLINEAR | BINARY SEARCH - "
        << "PERFORMANCE COMPARISON\n";

   for (int index = 0; index < NUMELS; index++)
   {
      if (index % 25 == 0)
      {
         cout << "\n\t";
      }
      cout << numbers[index] << " ";
   }

   cout << "\n";
}

/* **********************************************************
   Definition: binarySearch

   This function accepts numbers and NUMELS containing the
   number of elements in the array as arguments. It performs
   a binary search to find the number entered in the array
   and keeps track of the number of search-cycles it took to
   find it. If the number could not be found, a message is
   displayed.
   ********************************************************** */

int binarySearch(const int numbers[], const int userNum, int NUMELS)
{
   int firstElem = 0,
       lastElem = NUMELS - 1,
       midpoint = 0,
       numCycles = 0;

   bool numFound = false;

   while (firstElem <= lastElem && !numFound)
   {
      /* Calculate the midpoint */
      midpoint = (firstElem + lastElem) / 2;

      numbers[midpoint] == userNum ? numFound = true :
      numbers[midpoint] > userNum ? lastElem = midpoint - 1 :
                                    firstElem = midpoint + 1;

      numCycles++;
   }

   if (numFound == false)
   {
      cout << "\n\tBinary Search:\n";
      cout << "\n\tThe number " << userNum << " has not been found ...\n"
           << "\tNumber of search cycles: " << numCycles << "\n\n";
   }

   return numCycles;
}

/* **********************************************************
   Definition: displayComparison

   This function displays the numbers of comparisons it has
   taken to find the value for both linear and binary search,
   performed on an array containing n-number of integers.
   ********************************************************** */

void displayComparison(const int userNum, const int numCyclesLinear,
                       const int numCyclesBinary)
{

      cout << "\n\tLinear Search Cycles" << "\t" << "Binary Search Cycles\n"
           << "\t--------------------" << "\t" << "--------------------\n";

      cout << "\t" << numCyclesLinear << "\t\t\t" << numCyclesBinary << "\n";
}

Example Output: