c++ - 字符串的二进制搜索无法正常工作

标签 c++ binary-search

以下程序是库存菜单。出于某种原因,除了我搜索产品名称(选项 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;
}

最佳答案

您使用二进制搜索查找产品名称的代码是正确的,但数据似乎是按 SKU 排序的。二进制搜索算法仅在数据已排序时才有效。

您可以修改您的程序以在应用二进制搜索之前按产品名称对数据进行排序,但在这种情况下,由于您使用的是 N^2 搜索时间的冒泡排序,因此最好只使用线性搜索产品名称。

关于c++ - 字符串的二进制搜索无法正常工作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42189305/

相关文章:

python - 查找两个排序数组的中位数。是否可以消除一些不平等检查?

c# - 为什么会有 List<T>.BinarySearch(...)?

c++ - 将数学符号存储到字符串C++中

c++ - 为什么这个 C++11 中的 Singleton 不能正常工作?

c++ - 使用 boost 解析嵌套的 xml

c++ - 为什么当我放入偶数个元素时我的程序不工作

c# - 我可以对 guids 列表进行排序并进行二进制搜索吗?

c++ - 如何创建一个在执行时不显示任何窗口的cpp程序

c++ - 如何使用enable_if作为专门化的模板参数

c - 使用二分搜索在排序数组的正确位置插入一个元素以找到正确的位置,但是出现运行时错误