c++ - 为什么我的函数不返回正确的输出？

Question

我正在为类编写程序，要求我执行以下操作。将单词文件加载到字符串 vector 中，允许用户输入要搜索的单词，执行顺序搜索，使用选择排序对单词进行排序，最后执行二进制搜索。

除二分查找外，我设法使整个程序按预期工作。出于某种我无法理解的原因，我的顺序搜索功能正确显示所有信息，而二分搜索功能仅显示初始 cout。

感谢大家的帮助!

这是运行我的程序的当前输出的拷贝:

Enter the word to search for:
YELL
YELL was found successfully after 407 comparisons!
Perform selection sort...

Perform a binary search using selection sorted vector...

Press any key to continue . . .

我的程序代码(我知道没有人喜欢使用 using namespace std 但我需要为我的类(class)这样做):

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <fstream>

using namespace std;

void loadWords(vector<string>& words); // load unsorted words from file to vector of strings.

int sequentialSearch(vector<string>& words, string targetWord, int& count); // Perform sequential search and keep track of how many comparisons have happened.

void selectionSort(vector<string>& wordsSorted); // Perform the selection sort on the words.

int binarySearch(vector<string>& wordsSorted, string targetWord, int& count); // Perform binary search and keep track of how many comparisons have happened.

int main()
{
    vector<string> words;
    vector<string> wordsSorted;

    loadWords(words);
    wordsSorted = words;
    string targetWord;
    int count = 0;

    cout << "Enter the word to search for: " << endl;
    getline(cin, targetWord);

    sequentialSearch(words, targetWord, count);

    selectionSort(wordsSorted);

    binarySearch(words, targetWord, count);

    return 0;
}

void loadWords(vector<string>& words)
{

    ifstream inFile("unsortedBog.dat");

    string word;

    while (inFile >> word)
    {
        words.push_back(word);
    }
    inFile.close();
}

int sequentialSearch(vector<string>& words, string targetWord, int& count)
{
    for (int i = 0; i < words.size(); i++)
    {
        count++;
        if (words[i] == targetWord)
        {
            cout << targetWord << " was found successfully " << "after " << count << " comparisons!" << endl;
            return i;
        }
    }
    cout << "After performing " << count << " comparisons, " << targetWord << " could not be found." << endl;
}

void selectionSort(vector<string>& wordsSorted)
{
    cout << "Perform selection sort... \n" << endl;
    int min = 0;
    string min1;

    for (int i = 0; i < wordsSorted.size() - 1; i++)
    {
        if (wordsSorted[i] < wordsSorted[min])
        {
            min = i;
        }
        min1 = wordsSorted[i];
        wordsSorted[i] = wordsSorted[min];
        wordsSorted[min] = min1;

    }
}

int binarySearch(vector<string>& wordsSorted, string targetWord, int& count)
{
    cout << "Perform a binary search using selection sorted vector... \n" << endl;

    int first = 0,
        last = wordsSorted.size() - 1,
        mid,
        position = -1;
    bool found = false;

    while (!found && first <= last)
    {
        int i = 0;
        count = i++;
        mid = (first + last) / 2;
        if (wordsSorted[mid] == targetWord) // If value is found at mid
        {
            found = true;
            position = mid;
            cout << "The target word was located successfully after performing " << count << " comparisons.";
            return position;
        }
        else if (wordsSorted[mid] > targetWord) // Lower half
            last = mid - 1;
        else if (wordsSorted[mid] < targetWord) // Upper half
            first = mid + 1;
        else
            cout << "After performing " << count << " comparisons, the target word could not be found.";
    }
}

Answer 1

二分查找需要一个排序的数组。

您的 selectionSort() 远远不能完成对数组进行排序的任务。

它唯一做的就是在数组中搜索应该是排序列表中第一个单词的单词，将它移到数组中的第一个位置，并宣布“任务完成”。数组的其余部分保持未排序。

并且由于 binarySearch() 假定数组已排序，因此它完全偏离了轨道。

附言更糟糕的是，selectionSort() 一开始就无法搜索整个数组。它不查看数组中的最后一个元素。如果字典顺序的第一个单词在数组的最后一个元素中，它将找不到它。