C++ Finding the last occurrence of an int in a linear search

Question

This week for homework I've been tasked with loading in a text file of 1,000 numbers and to do a linear search of a number entered in by a user. I have the linear search part done, but I have to find and print the last occurrence of that integer. I figured it would be easiest to run the array from the end and print the last occurrence and break the loop. I've started the code, but am having some trouble at finding the last occurrence.

I know my second for loop to run the array backwards is wrong, I'm just not sure what about it is wrong. Any help is appreciated! Thank you!

#include <iostream>
#include <fstream>
#include <conio.h>

using namespace std;

int main()
{
    ifstream input("A1.txt");
    int find;

    cout << "Enter a number to search for: ";
    cin >> find;

    if (input.is_open())
    {
        int linSearch[1000];

        for (int i = 0; i < 1000; i++)
        {
            input >> linSearch[i];

            for (i = 1000; i > 0; i--)
            {
                if (find == linSearch[i])
                {
                    cout << find << " is at position " << i << ". " << endl;
                }
            }
        }
    }

    _getch();
    return 0;
}

Hint: what is the last index in `int[1000]`? – Beta Oct 25 '16 at 02:19 — Beta, Oct 25 '16 at 02:19
I see now. Thank you! @Beta – Justin Farr Oct 25 '16 at 02:27 — Justin Farr, Oct 25 '16 at 02:27

Sam Varshavchik · Accepted Answer · 2016-10-25T02:40:21.410

    for (int i = 0; i < 1000; i++)
    {
        input >> linSearch[i];

This is a good start. You started a loop to read the 1000 numbers into your array.

        for (i = 1000; i > 0; i--)

Don't you think this is a bit premature? You haven't yet finished the loop to read the 1000 numbers in the file, yet, and you're already searching the array, that hasn't been fully read yet. There's a very technical term for this logical mistake: "putting the cart before the horse". You need to finish the loop to read the 1000 numbers, first. And only then you can execute this second loop.

        {
            if (find == linSearch[i])

Ok, now let's back up a bit. You started the loop with i=1000. Now, right here, what is the very first value if i? It is 1000. Don't you see a problem here? The 1000 element array, "linSearch", as you know, contains values numbered 0 through 999. That's a 1000 elements total. With i starting off with a value of 1000, accessing the non-existent linSearch[1000] is undefined behavior, and a bug.

You could tweak the logic here, to get it right. But it's not even necessary to do that. You already have a perfectly working loop that reads the 1000 numbers from the file. And you know which number you want to search.

So, each time you read the next number from the file, if it's the number you're looking for, you just store its position. So, when all is said and done, the last position that's stored in that variable will be the position of the last occurrence of the number you're searching for. Simple logic. All you have to do is also set a flag indicating that the number you were searching for has been found.

And once you come to the decision to do that, you will find that it's no longer even needed to have any kind of an array in the first place. All you have to do is read the 1000 numbers from the file, one number at a time, check if each number is the one you're searching for, and if so, save its position. Then, at the end of the loop, compare notes.

I wish I didn't have to work with the arrays, but professor's orders! I solved my issue now, though. Thank you! — Justin Farr, Oct 25 '16 at 02:35

score 1 · Answer 2 · answered Oct 25 '16 at 02:21

Since it's homework, I should probably be at least a little vague, and I definitely shouldn't use code.

You should not be nesting the 2nd loop within the first loop. It should be at the same indentation level as, and after the closing bracket for, the first loop.

Also, you shouldn't be searching back to 0 in almost all cases, but instead back to where you found the element in your linear search, or where you find it, and no further.

And yes, pay attention to what Beta wrote.

Also, shouldn't you break out of the loop each time you find what you're looking for?

C++ Finding the last occurrence of an int in a linear search

2 Answers2