Counting Search Comparisons C++

Question

This program searches for a user entered word in a dictionary text file and outputs what line it is on. I need to count the number of comparisons made to find the word in both a linear and binary search. Right now it says there were zero comparisons made. Any ideas on where or how to implement these counters would be much appreciated.

string linearSearch(const vector<string> &L, string k);
string binarySearch(const vector<string> &L, string k, int a = 0, int b = -1);
int count1 = 0;
int count2 = 0;

int main()
{

    ifstream inFile;
    inFile.open("dictionary.txt");

    vector < string > words;
    string line;

    while (getline(inFile, line))
    {
        words.push_back(line);
    }

    inFile.close();
    string userWord;
    cout << "Search for a word: " << endl;
    cin >> userWord;

    if (words.empty())
    {
        return -1;
    }

    cout << "Using binary search, the word " << userWord << " is in slot "
            << binarySearch(words, userWord) << ". There were " << count2
            << " comparisons  made." << endl;

    cout << "Using linear search, the word " << userWord << " is in slot "
            << linearSearch(words, userWord) << ". There were " << count1
            << " comparisons made." << endl;

    return 0;
}
string linearSearch(const vector<string> &L, string k)
{

    for (int i = 0; i < L.size(); ++i)
    {
        count1++;
        if (L[i] == k)
        {
            count1++;
            return to_string(i);
        }
    }
    return to_string(-1);

}
string binarySearch(const vector<string> &L, string k, int a, int b)
{

    ++count2;
    if (b == -1)
    {
        b = L.size();
    }
    int n = b - a;

    if (n == 0)
    {
        return to_string(-1); //?
    }

    int mid = (a + b) / 2;

    if (L[mid] == k)
    {
        ++count2;
        return to_string(mid);
    }
    else if (L[mid] > k)
    {
        ++count2;
        return binarySearch(L, k, a, mid);
    }
    else
    {
        count2 += 2;
        return binarySearch(L, k, mid + 1, b);
    }
    return to_string(-1);

}

scohe001 · Accepted Answer · 2018-01-22T21:49:55.067

Uh oh, this looks like undefined behavior caused by Sequence Points (see this question for more information).

To quote the answer in that question,

the order of evaluation of operands of individual operators and subexpressions of individual expressions, and the order in which side effects take place, is unspecified.

You're trying to perform a set and a get on the same variable (one of the count's) in the same sequence point. Which will happen first (the set or the get) is undefined.

Split your cout's into two and everything should be solved.

cout << "Using binary search, the word "<< userWord << " is in slot " << 
    binarySearch(words,userWord) << ".";
cout << "There were " << count2 << " comparisons made." << endl;

cout << "Using linear search, the word "<< userWord << " is in slot " << 
    linearSearch(words,userWord) << ".";
cout << "There were " << count1 << " comparisons made." << endl;

Counting Search Comparisons C++

1 Answers1