Seeking help with Sequential Search Algorithm

[dub1987]

The details of the assignment is within the code. Basically its a simulated radio station holding a number guessing contest. 20 numbers were "randomly selected" and stored in a text file. The sequential search algorithm is to find the number (obviously), but I am stuck at this point... could someone give me a nudge to get me rolling again please?

#include<iostream>
#include<fstream>

using namespace std;

int sequenSrch(int&, int&);
int guess();

int main()
{
	cout << "This program simulates a radio station that asks the caller to guess a number.\n";
	cout << "The number is compared against a list of 20 numbers between 1 and 500 inclusive.\n";
	cout << "The contest is held until a number has been matched or a value of - 1 is entered.\n";
	cout << "A message is displayed containing the winning number, the location in the list of numbers,";
	cout << " the number of calls made, and the amount of the prize.";

	int num = 20;
	int size = 0;
	int first, x;
	int* prizeArray = new int[num];
	int location;
	
	location = sequenSrch(); // Not sure what to pass here...?

	ifstream prizeList;
	
	prizeList.open("prizeList.txt");
	while (prizeList >> x)
	{
		if (size == num)
		{
			int* newPrizeArray = new int[2 * num];

			for (first = 0; first < size; first++)
			{
				newPrizeArray[first] = prizeArray[first];
			}
			delete[] prizeArray;
			prizeArray = newPrizeArray;
			num *= 2;
		}
		prizeArray[size] = x;
		size++;
	}
	prizeList.close();

	guess();
	;

	return 0;
}

int sequenSrch(int newPrizeArray[20], int value)
{
	int i = 1, results = 0;
	bool found = false;
	
	while (!found && i < newPrizeArray[20])
	{
		if (newPrizeArray[i] == value)
		{
			found = true;
			results = i;
		}
		cout << guess() << " is not in the list. Call again.\n";
		i++;
	}
	return results;
}

int guess()
{
	int guess;

	cout << "Hello caller. What number between 1 and 500 are you guessing?\n";
	cin >> guess;

	return guess;
}

[benbalach]

* Remove all occurrences of newPrizeArray from your code.

* Change prizeArray from a regular plain C style array to a std::vector<int>.

* Pass the prizeArray by const reference to sequenSrch().

* Remove the while loop in main() and replace it with std::copy(std::istream_iterator<int>{prizeList}, std::istream_iterator<int>{}, std::back_inserter(prizeArray). You will have to #include <iterator> and #include <algorithm> .

This will reduce the size of your code substantially making it easier to read and understand.

[dub1987]

I haven't learned about vector< > just yet. I re-coded most of main and re-coded sequenSrch() here is what I came up with.... still not complete but closer (I think)...

	const int x = 20;
	int y;
	int prizeArray[x];
	
	ifstream prizeList;
	
	prizeList.open("prizeList.txt");
	for (y = 0; y < x && prizeList >> prizeArray[y]; y++);
	prizeList.close();

	guess();
	sequenSrch(); //"+3 overloads"... not sure what to pass (still)

	return 0;
}

int sequenSrch(const int prizeArray[], int arrayLength, int searchedItem)
{
	int location;
	bool found = false;
	location = 0;
	
	while (location < arrayLength && !found)
	if (prizeArray[location] == searchedItem)
		found = true;
	else
		cout << guess() << " is not in the list. Call Again.\n";
		location++;

	if (found)
		return location;
	else
		return -1;
}

[dub1987]

Here is what I have now:

#include<iostream>
#include<fstream>

using namespace std;

int sequenSrch(const int prizeArray[], int arrayLength, int searchedItem);
int guess();

int main()
{
	cout << "This program simulates a radio station that asks the caller to guess a number.\n";
	cout << "The number is compared against a list of 20 numbers between 1 and 500 inclusive.\n";
	cout << "The contest is held until a number has been matched or a value of - 1 is entered.\n";
	cout << "A message is displayed containing the winning number, the location in the list of numbers,";
	cout << " the number of calls made, and the amount of the prize.";

	const int x = 20;
	int fillArray;
	int prizeArray[x];
	int callerNum = 1;

	ifstream prizeList;
	
	prizeList.open("prizeList.txt");
	for (fillArray = 0; fillArray < x && prizeList >> prizeArray[fillArray]; fillArray++);
	prizeList.close();

	int guessNum = guess();
	int loc = sequenSrch(prizeArray, fillArray, guessNum);
	
	
	while (guessNum != loc)
	{
		guess();
		callerNum++;
	}
		cout << "Congratulations. Your number " << guessNum << " was found at location " << loc;
		cout << " of the list.\n";
		cout << "Counting you, there were " << callerNum << " callers.You win $10, 000!\n";

	return 0;
}

int sequenSrch(const int prizeArray[], int arrayLength, int searchedItem)
{
	int location;
	bool found = false;
	location = 0;
	
	while (location < arrayLength && !found)
	if (prizeArray[location] == searchedItem)
		found = true;
	else
		location++;

	if (found)
		return location;
	else
		return -1;
}

int guess()
{
	int guess;

	cout << "\nHello caller. What number between 1 and 500 are you guessing?\n";
	cin >> guess;

	return guess;
}

I keep getting an infinite loop that keeps asking for the guess or an infinite scrolls the console until I exit. My head is about to explode from looking at this simple program that I just cannot seem to figure out.

[benbalach]

After you assign the return value of sequenSrch(prizeArray, fillArray, guessNum) to loc print out the value of loc to see what it is.

You are getting an infinite loop because the each time you call guess() the return value is never equals to loc.

The bug might be somewhere in sequenSrch(), those if and else statements look suspicious to me.

[dub1987]

That block of code works just fine. I did output it before I started writing the loop to see if it was working correctly and it was. But I'll look harder at the loop within main.

[Smac89]

The infinite loop problem is from line 34 of your code. This is because you did not capture the value returned by guess, so as soon as execution enters that while loop, it stays there forever because your condition will never change.

The condition you are using is also wrong because say one of the numbers in the list was 100 and your list happens to contain 100, the sequenSrch function will return the location of 100 but since your list only contains 20 numbers, the program will still say that the user guessed wrong. A better condition will be:

while (loc == -1) {...}

Also your search loop could be condensed to just:

for (int v = 0; v < arrayLength; v++) {
    if (prizeArray[v] == searchedItem)
	return v;
}
return -1

[dub1987]

Things that make me go "hmmm..." The search loop was a mirror image of that in my book, that is why it is the way it is. But I like your suggestion better because it is condensed. I have since figured this whole thing out by changing the while loop to display if the guessed number is incorrect. Then I used if the number guessed is in the list.... display winner message, else the number entered was -1 so terminate. I really appreciate all the input. You guys have helped me out a bunch!