C++二分查找函数不一致

Question

在大多数情况下，我创建的以下二进制搜索功能都有效。然而，有时没有明显的原因，当我知道它存在时搜索将找不到条目。有时，search 的变量将包含用户输入的内容，但缺少第一个字母。我已经附加了 cin.clear() 和 cin.ignore() 来尝试修复这个奇怪的错误。到目前为止，在添加 cin.clear() 之后，我无法重现该问题。

查看以下节目：

void searchInventory(vector<Vehicle> &carList)
{
    cout << "You have chosen to search for a vehicle.\n\n";

        int  first = 0,                     // first, last, and  middle define the vector element subscripts
             last = (carList.size() - 1),
             middle,
             position = -1,                 // Needed to keep track of current position
             searchResult = 0;              // Used copy the data from position for use in displaying confirmation messages to the screen
        bool found = false;                 // Flag to tell program if search has been successful
        string search;                      // Used to hold user's input on what to search

        do
        {
            // Prompt to user so they can enter the make they are searching for
            cout << "Please enter the make of the vehicle you are searching for: ";
            cin.ignore();
            cin.clear();
            getline(cin, search);

            cout << endl; 

            // Binary search algorithm begins...
            while (!found && first <= last)
            {
                middle = (first + last) / 2;
                if (carList[middle].getMake() == search)
                {
                    found = true;
                    position = middle;
                }

                else if (carList[middle].getMake() > search)
                    last = middle - 1;

                else
                    first = middle + 1;
            }

            searchResult = position;  // position is copied into searchResult

            if (searchResult == -1)   // if searchResult is -1, then the user specified word was not found
            {
                cout << "Sorry, there is no vehicles under the make of " << search << " in your inventory\n"
                     << "Please try again...\n\n";
            }

            else
            {
                // If the make was found, the information about the first vehicle with the specified model is given
                cout << search << "has been found...\n";

            }

        } while (searchResult == -1);
    }
}

此函数的一些背景知识：我正在向量对象中搜索包含汽车品牌的字符串数据类型的成员变量。

例如，如果我在向量中存在 "Ford" 时搜索 "Ford"，程序大部分会说

Ford has been found

但其他时候程序会说

Sorry, there is no vehicles under the make of Ford in your inventory

其他时候程序会说

Sorry, there is no vehicles under the make of ord in your inventory

注意最后一个 "ord" 而不是 "Ford"。

有谁知道为什么这个二分搜索函数如此难以预测？

Answer 1

要了解您的代码为何无法运行，您需要对其进行调试或至少添加一些调试输出。如果你添加类似

cout << "Now compare: " << carList[middle].getMake() << endl;

在 if (carList[middle].getMake() == search) 之前，您会发现有时（在第一次输入之后）您的程序不会比较任何东西，因为您没有重新初始化变量 found、first 和 last.

您需要删除 cin.ignore();，这就是您错过第一个字符的原因。

更正后的代码：

void searchInventory(vector<Vehicle> &carList) {
    cout << "You have chosen to search for a vehicle.\n\n";

    string search;                      // Used to hold user's input on what to search
    int searchResult = 0;
    do {
        // Prompt to user so they can enter the make they are searching for
        cout << "Please enter the make of the vehicle you are searching for: ";
        cin.clear();
        getline(cin, search);

        cout << endl;

        int first = 0,                      // first, last, and  middle define the vector element subscripts
            last = (carList.size() - 1),
            middle,
            position = -1;                  // Used copy the data from position for use in displaying confirmation messages to the screen
        bool found = false;                 // Flag to tell program if search has been successful

        // Binary search algorithm begins...
        while (!found && first <= last) {
            middle = (first + last) / 2;
            if (carList[middle].getMake() == search) {
                found = true;
                position = middle;
            } else if (carList[middle].getMake() > search) {
                last = middle - 1;
            } else {
                first = middle + 1;
            }
        }
        searchResult = position;  // position is copied into searchResult

        if (searchResult == -1) { // if searchResult is -1, then the user specified word was not found
            cout << "Sorry, there is no vehicles under the make of " << search << " in your inventory\n"
                 << "Please try again...\n\n";
        } else {
            // If the make was found, the information about the first vehicle with the specified model is given
            cout << search << " has been found...\n";
        }
    } while (searchResult == -1);
}

也不要将输入与您的算法相结合。您最好创建更通用的函数，例如 int vehicle_search(vector<Vehicle>& list, const string& search) 向量中车辆的 return 索引，如果未找到则 -1。（仅作为示例，您还可以 return 指向元素或迭代器的指针，并传递 Vehicle 而不是 string）。然后您将从程序中的某处调用它，检查 return 值并输出结果。

C++二分查找函数不一致

C++ binary search function inconsistent

c++

vector

object

binary-search