二進制搜索字符串無法正常工作

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搜索時間，因此只需一個線性搜索產品名稱。