Modify the binary search function presented in chapter 9 so that it takes two pa

Question

Modify the binary search function presented in chapter 9 so that it takes two parameters: a const vector of Persons (which will already be sorted by name), and the name of the Person being searched for (use the Person class from Project 4.b). Because a vector knows its own length, no size parameter is needed. If the Person object with the matching name is found in the vector, the index of its position should be returned. Otherwise it should return -1. Because the vector of Persons is being passed by const, you'll need to make the getName() method a constant member function, to reassure the compiler that the getName() method isn't changing any Person objects.

The files must be named Person.hpp, Person.cpp and personSearch.cpp

*************Existing Person.hpp*************************************************************

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

class Person
{

public:  
   Person(void);
   Person(std::string n, double a);                   //Constructor
   std::string getName();
   double getAge();

private:
   std::string nameMember;
   double ageMember;  
};

************************Existing Person.cpp******************************************

#include <iostream>
#include <string>
#include "Person.hpp"
#include <vector>
using namespace std;

Person::Person(void)
{
   nameMember = " ";
   ageMember = 0;
}

Person::Person(std::string nameIn, double ageIn)
{
   std::string name = nameIn;
   ageMember = ageIn;
}

std::string Person::getName()
{
   return nameMember;
}

double Person::getAge()
{
   return ageMember;
}

************This is the binarySearch Code that needs to be modified************************************************

#include "Person.hpp"
#include <iostream>
#include <vector>
using namespace std;

// Function prototype
int binarySearch(const int [], int, int);

const int SIZE = 20;

int main()
{
   // Create an array of ID numbers sorted in ascending order
   int IDnums[SIZE] = {101, 142, 147, 189, 199, 207, 222,
       234, 289, 296, 310, 319, 388, 394,
       417, 429, 447, 521, 536, 600 };

   int empID, // Holds the ID to search for
       results; // Holds the search results

   // Get an employee ID to search for
   cout << "Enter the employee ID you wish to search for: ";
   cin >> empID;

   // Search for the ID
   results = binarySearch(IDnums, SIZE, empID);

   // If binarySearch returned -1, the ID was not found
   if (results == -1)
       cout << "That number does not exist in the array. ";
   else
   { // Otherwise results contains the subscript of
       // the specified employee ID in the array
       cout << "ID " << empID << " was found in element "
           << results << " of the array. ";
   }
   return 0;
}

/*****************************************************************
* binarySearch *
* This function performs a binary search on an integer array *
* with size elements whose values are stored in ascending *
* order. The array is searched for the number stored in the *
* value parameter. If the number is found, its array subscript *
* is returned. Otherwise, -1 is returned. *
*****************************************************************/

int binarySearch(const int array[], int size, int value)
{
   int first = 0, // First array element
       last = size - 1, // Last array element
       middle, // Midpoint of search
       position = -1; // Position of search value
   bool found = false; // Flag

   while (!found && first <= last)
   {
       middle = (first + last) / 2; // Calculate midpoint
       if (array[middle] == value) // If value is found at mid
       {
           found = true;
           position = middle;
       }
       else if (array[middle] > value) // If value is in lower half
           last = middle - 1;
       else
           first = middle + 1; // If value is in upper half
   }
   return position;
}

Explanation / Answer

/*****************************************************************

* i am assuming you rest of the code is working fine*

* modified binarySearch *

* This function performs a binary search on an person vector *

* which will already be sorted by name) *

If the number is found, its vector index of its position *

* is returned. Otherwise, -1 is returned. *

* assuming that names are case sensetive *

* NOTE: FOR return value of compare function for two string

* 0 They compare equal

<0 Either the value of the first character that does not match is lower in the compared string, or all compared characters match but the compared string is shorter.

>0 Either the value of the first character that does not match is greater in the compared string, or all compared characters match but the compared string is longer.

*****************************************************************/

int binarySearch(const vector<Person>array,string value)

{

int first = 0, // First array element

last = array.size() - 1, // Last array element

middle, // Midpoint of search

position = -1; // Position of search value

bool found = false; // Flag

while (!found && first <= last)

{

middle = (first + last) / 2; // Calculate midpoint

int result=value.compare(array[middle].getName());

if (result== 0) // If value is found at mid

{

found = true;

position = middle;

}

else if (result<0) // If value is in lower half

last = middle - 1;

else

first = middle + 1; // If value is in upper half

}

return position;

}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.