Binary Search for String not working correctly

Question

The following program is an Inventory Menu. For some reason everything seems to work except when I searching for the name of the product (option 3) function lookupName. It was working before I put a condition to where if nothing was returned, to give an error message, which is the same I used for lookupSku and that one is working fine. I am not sure what is wrong with the code anymore.

#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdlib>
using namespace std;
struct inventory {
 string name;
 int sku;
 int quantity;
 double price;
};
int size = 0;
void fillArray ( inventory[], int&, ifstream& );
void sortArray ( inventory[], int );
void displayIn ( inventory[], int );
int lookupSku ( inventory[], int, int );
int lookupName ( inventory[], int, string );
int main(){
 // Constants for menu choices
 const int DISPLAY_INVENTORY = 1,
 LOOKUP_SKU = 2,
 LOOKUP_NAME = 3,
 QUIT_CHOICE = 4;
 int choice;
 inventory products [100];
 ifstream fin;
 fin.open ("inventory.dat");
 if (!fin)
 {
 cout << endl << endl
 << " ***Program Terminated. *** " << endl << endl
 << " Input file failed to open. " << endl;
 system ( "PAUSE>NUL" );
 return 1;
 }
 fillArray ( products, size, fin );
 sortArray ( products, size );
 // Set up numeric output formatting.
 cout << fixed << showpoint << setprecision(2);
 do
 {
 // Display the menu.
 cout << "\n\t\t Manage Inventory Menu\n\n"
 << "1. Display inventory sorted by sku\n"
 << "2. Lookup a product by sku\n"
 << "3. Lookup a product by name\n"
 << "4. Quit the Program\n\n"
 << "Enter your choice: ";
 cin >> choice;
 cout << endl;
 // Validate the menu selection.
 while (choice < DISPLAY_INVENTORY || choice > QUIT_CHOICE)
 {
 cout << "Please enter a valid menu choice: ";
 cin >> choice;
 }
 // Validate and process the user's choice.
 if (choice != QUIT_CHOICE)
 {
 int indexSku,
 indexName,
 skuChoice;
 string nameChoice;
 switch (choice)
 {
 case DISPLAY_INVENTORY:
 displayIn ( products, size );
 break;
 case LOOKUP_SKU:
 cout << "Enter the Sku number: ";
 cin >> skuChoice;
 cout << endl;
 indexSku = lookupSku( products, size, skuChoice );
 if ( indexSku >= 0 )
 {
 cout << "Product Name: " << products[indexSku].name << endl
 << "Sku: " << products[indexSku].sku << endl
 << "Quantity: " << products[indexSku].quantity << endl
 << "Price: " << products[indexSku].price << endl;
 }
 else
 cout << "No product found with this sku!" << endl;
 break;
 case LOOKUP_NAME:
 cout << "Enter product name with no spaces: ";
 cin >> nameChoice;
 cout << endl;
 indexName = lookupName( products, size, nameChoice );
 if ( indexName >= 0 )
 {
 cout << "Product Name: " << products[indexName].name << endl
 << "Sku: " << products[indexName].sku << endl
 << "Quantity: " << products[indexName].quantity << endl
 << "Price: " << products[indexName].price << endl;
 }
 else
 cout << "No product found with this product name!" << endl;
 break;
 }
 }
 } while (choice != QUIT_CHOICE);
 fin.close ();
 return 0;
}
void fillArray ( inventory product[], int &size, ifstream &fin )
{
 int counter = 0;
 while (fin >> product[counter].name)
 {
 fin >> product[counter].sku>> product[counter].quantity
 >> product[counter].price;
 counter ++;
 }
 size = counter;
}
void sortArray ( inventory product[], int size )
{
 bool swap;
 do
 {
 swap = false;
 for (int count = 0; count < (size - 1); count++)
 {
 if ( product[count].sku > product[count + 1].sku )
 {
 inventory temp = product[count];
 product[count] = product[count + 1];
 product[count + 1] = temp;
 swap = true;
 }
 }
 } while (swap);
}
void displayIn ( inventory product[], int size )
{
 for ( int i = 0; i < size; i++ )
 cout << product[i].sku << " " << product[i].quantity << " "
 << product[i].price << " " << setw(4) << product[i].name << endl;
}
int lookupSku(inventory product[], int size, int value)
{
 int first = 0,
 last = size - 1,
 middle,
 position = -1;
 bool found = false;
 while (!found && first <= last)
 {
 middle = (first + last) / 2;
 if (product[middle].sku == value)
 {
 found = true;
 position = middle;
 }
 else if (product[middle].sku > value)
 last = middle - 1;
 else
 first = middle + 1;
 }
 return position;
}
int lookupName ( inventory product[], int size , string value )
{
 int first = 0,
 last = size - 1,
 middle,
 position = -1;
 bool found = false;
 while (!found && first <= last)
 {
 middle = (first + last) / 2;
 if (product[middle].name == value)
 {
 found = true;
 position = middle;
 }
 else if (product[middle].name > value)
 last = middle - 1;
 else
 first = middle + 1;
 }
 return position;
}

• πάντα ῥεῖ: The right tool to solve such problems is your debugger. You should step through your code line-by-line before asking on Stack Overflow. For more help, please read How to debug small programs (by Eric Lippert). At a minimum, you should [edit] your question to include a Minimal, Complete, and Verifiable example that reproduces your problem, along with the observations you made in the debugger.

Answer 1

You code for looking up the product name using Binary Search is correct, but it appears that the data is sorted by SKU. The Binary Search algorithm will only work if the data is sorted.

You could modify your program to sort the data by product name before applying the Binary Search, but in this case since you are using a Bubble Sort which is an N^2 search time, you would be better off with just a linear search for the product name.

• Maria Fernanda: you are absolutely correct, I just did a linear search and it fixed the problem. Thanks a lot!