Implement binary search with string array instead of int array

Question

The program is supposed to incorporate this into it. I created most of the code, but this is a second part of my lab where I have to go back and input strings for the binary search instead. I don't get how to search for strings if I have to remove the idNum and the results and empId.

    const int NUM_NAMES = 20;
       string names[NUM_NAMES] = {"Collins, Bill", "Smith, Bart", "Allen, Jim",
                                   "Griffin, Jim", "Stamey, Marty", "Rose, Geri",
                                   "Taylor, Terri", "Johnson, Jill", "Allison, Jeff",
                                   "Looney, Joe", "Wolfe, Bill", "James, Jean",
                                   "Weaver, Jim", "Pore, Bob", "Rutherford, Greg",
                                   "Javens, Renee", "Harrison, Rose", "Setzer, Cathy",
                                   "Pike, Gordon", "Holland, Beth" };

So, the binary search will work with strings instead of int. I don't understand how to do it.

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

    int main()
    {

        // Array with employee IDs 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 results;   // To hold the search results
       int empID;     // To hold an employee ID

       // 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 results contains -1 the ID was not found.
       if (results == -1)
          cout << "That number does not exist in the array.\n";
       else
       {
          // Otherwise results contains the subscript of
          // the specified employee ID in the array.
          cout << "That ID is found at element " << results;
          cout << " in the array.\n";
       }
       return 0;
    }

The binarySearch function performs a binary search on an integer array. array, which has a maximum of size elements, is searched for the number stored in value. If the number is found, its array subscript is returned. Otherwise, -1 is returned indicating the value was not in the array.

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

   while (!found && first <= last)
   {
      middle = (first + last) / 2;     // Calculate mid point
      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;
}

Axalo · Accepted Answer · 2015-04-14 17:50:22Z

1

Change

int binarySearch(const int array[], int size, int value)

to

int binarySearch(const std::string array[], int size, const std::string &value)

and then use it as follows

std::string name;
std::getline(std::cin, name); // read name from console
std::sort(names, names + NUM_NAMES); // make sure the array is sorted
results = binarySearch(names, NUM_NAMES, name);

You could also make use of templates so your code is more generic

template<typename T>
int binarySearch(const T array[], int size, const T &value)

edited Apr 14, 2015 at 17:50

answered Apr 14, 2015 at 17:46

Axalo

3,0384 gold badges27 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mary Over a year ago

In the sort function, why do I do "names + NUM_NAMES"? How would I show that in a prototype?

Collectives™ on Stack Overflow

Implement binary search with string array instead of int array

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related