Homework help, Search Benchmarks

Question

C++ Beginner 0 Junior Poster in Training

14 Years Ago

Problem:
Write a program that has an array of at least 20 integers. It should call a function that uses the linear search algoritm to locate one of the values. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that uses the binary search algorithm to locate the same value. It should also keep count of the number of comparisons it makes. Display these values on the screen.

I have successfully got the searchList to work however the binary search is not going so good. I got 1 error when trying to compile it. If anyone could help I would greatly appreciate it, also if you can explain why, etc so I have a better comprehension of what needs to be changed I would greatly appreciate it.

Last note: it requires that we create a function that counts how many searchs it took until it did or didnt find the entry into the program. However looking over the chapter I cannot locate how to even fathom how to do so, any help in that error is a bonus!!

Errors Received:
1. error C4430: missing type specifier - int assumed. Note: C++ does not support default-int

#include <iostream>
using namespace std;

int searchList(const int [], int, int);
int binarySearch(const int [], int, int);

int main()
{
	int const SIZE = 20;
	int access[SIZE] = {01, 12, 23, 34, 45, 56, 67, 78, 89, 90,
						 123, 234, 345, 456, 567, 678, 789, 890, 901, 1000};
	int resultSearch;
	int resultsBinary;
	int pin;

	cout << "Please enter a valid PIN Number: ";
	cin >> pin;

	cout << "I will search for the PIN number using searchList function\n";

	resultSearch = searchList(access, SIZE, pin);

	if(resultSearch == -1)
		cout << "You did not enter a valid PIN number.\n";

	else
	{
		cout << "You entered a valid PIN number\n";
		cout << (resultSearch + 1) << "\n";
	}

	cout << "I will now search for the PIN number using the Binary seach function.\n";

	resultsBinary = binarySearch(access, SIZE, pin);
	
	if(resultsBinary == -1)
		cout << "You have entered an invalid PIN number.\n";

	else
	{
		cout << "You have entered a valid PIN number.\n";
		cout << resultsBinary << endl;
	}

	return 0;
}
int searchList(const int list[], int size, int value)
{
	int index = 0,
		position = -1;
	bool found = false;

	while(index < size && !found)
	{
		if(list[index] == value)
		{
			found = true;
			position = index;
		}
		index++;
	}
	return position;
}
binarySearch(const int list[], int size, int value)
{
	int first = 0,
		last = size -1,
		middle,
		position = -1;
	bool found = false;

	while(!found && first <= last)
	{
		middle = (first + last) / 2;
		if (list[middle] == value)
		{
			found = true;
			position = middle;
		}
		else if (list[middle] > value)
			last = middle - 1;
		else
			first = middle +1;
	}
	return position;
}

c++

Edited 14 Years Ago by C++ Beginner because: n/a

3 Contributors
4 Replies
2K Views
1 Day Discussion Span
Latest Post 14 Years Ago Latest Post by hag++

All 4 Replies

hag++ 24 Junior Poster

14 Years Ago

Also, a smal logical problem :

int searchList(const int list[], int size, int value)
{
	int index = 0,
		position = -1;
	bool found = false;

	while(index < size && !found)
	{
		if(list[index] == value)
		{
			found = true;
			position = index;
		}
		index++;
	}
	return position;
}

The index will be incremented one more time even if the PIN is found because it runs one more time after the flag is set to true. If the PIN is located, you want to return that position. Like this:

int searchList(const int list[], int size, int value)
{
	int index = 0,

	while(index < size)
	{
		if(list[index] == value)
		return index;

		index++;
	}
	return -1; // Indicates PIN not found
}

Edited 14 Years Ago by hag++ because: forgot something

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

C++ Beginner 0 Junior Poster in Training · Answer 1 · 2010-01-19T02:43:17+00:00

C++ Beginner 0 Junior Poster in Training

14 Years Ago

.

Edited 14 Years Ago by C++ Beginner because: n/a

jBat -3 Light Poster · Answer 2 · 2010-01-19T05:41:45+00:00

Problem:
Write a program that has an array of at least 20 integers. It should call a function that uses the linear search algoritm to locate one of the values. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that uses the binary search algorithm to locate the same value. It should also keep count of the number of comparisons it makes. Display these values on the screen.
I have successfully got the searchList to work however the binary search is not going so good. I got 1 error when trying to compile it. If anyone could help I would greatly appreciate it, also if you can explain why, etc so I have a better comprehension of what needs to be changed I would greatly appreciate it.
Last note: it requires that we create a function that counts how many searchs it took until it did or didnt find the entry into the program. However looking over the chapter I cannot locate how to even fathom how to do so, any help in that error is a bonus!!
Errors Received:
1. error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
#include <iostream>
using namespace std;

int searchList(const int [], int, int);
int binarySearch(const int [], int, int);

int main()
{
	int const SIZE = 20;
	int access[SIZE] = {01, 12, 23, 34, 45, 56, 67, 78, 89, 90,
						 123, 234, 345, 456, 567, 678, 789, 890, 901, 1000};
	int resultSearch;
	int resultsBinary;
	int pin;

	cout << "Please enter a valid PIN Number: ";
	cin >> pin;

	cout << "I will search for the PIN number using searchList function\n";

	resultSearch = searchList(access, SIZE, pin);

	if(resultSearch == -1)
		cout << "You did not enter a valid PIN number.\n";

	else
	{
		cout << "You entered a valid PIN number\n";
		cout << (resultSearch + 1) << "\n";
	}

	cout << "I will now search for the PIN number using the Binary seach function.\n";

	resultsBinary = binarySearch(access, SIZE, pin);
	
	if(resultsBinary == -1)
		cout << "You have entered an invalid PIN number.\n";

	else
	{
		cout << "You have entered a valid PIN number.\n";
		cout << resultsBinary << endl;
	}

	return 0;
}
int searchList(const int list[], int size, int value)
{
	int index = 0,
		position = -1;
	bool found = false;

	while(index < size && !found)
	{
		if(list[index] == value)
		{
			found = true;
			position = index;
		}
		index++;
	}
	return position;
}
binarySearch(const int list[], int size, int value)
{
	int first = 0,
		last = size -1,
		middle,
		position = -1;
	bool found = false;

	while(!found && first <= last)
	{
		middle = (first + last) / 2;
		if (list[middle] == value)
		{
			found = true;
			position = middle;
		}
		else if (list[middle] > value)
			last = middle - 1;
		else
			first = middle +1;
	}
	return position;
}

you are missing the int before the implementation of the function binarySearch.

[B]int[/B] binarySearch(const int list[], int size, int value)
{
	int first = 0,
		last = size -1,
		middle,
		position = -1;
	bool found = false;

hag++ 24 Junior Poster · Answer 3 · 2010-01-19T23:08:42+00:00

*EDIT: Sorry, upon second look I see you return position and not index, so it would work, the second vers of the code is a little more concise/ clear tho and you dont need as many variables

Homework help, Search Benchmarks

Recommended Answers Collapse Answers

All 4 Replies

Recommended Answers