Двоичный поиск строки не работает правильно

Question

Следующая программа представляет собой меню инвентаря. По какой-то причине все работает, за исключением случаев, когда я ищу имя функции продукта (опция 3) lookupName. Он работал до того, как я поставил условие на то, где, если ничего не было возвращено, чтобы дать сообщение об ошибке, которое я использовал для lookupSku, и что он работает нормально. Я не уверен, что не так с кодом больше.

#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; 
} 

Answer 1

Код для поиска имени продукта с помощью двоичного поиска является правильным, но, похоже, данные сортируются по SKU. Алгоритм двоичного поиска будет работать, только если данные будут отсортированы.

Вы можете изменить свою программу для сортировки данных по названию продукта перед применением двоичного поиска, но в этом случае, поскольку вы используете сортировку пузырьков, которая является поисковым временем N^2, вам будет лучше с помощью всего лишь линейный поиск имени продукта.