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;
}