Question

C++

For this assignment, you will create a search benchmark, that is a comparison between the Linear and Binary Search algorithm on the same list of names provided in a text file.

1. Ask the user to enter a filename
2. Ask the user to enter a name; this is the search item.
3. Loop until you reach the end of the file and read all the names and store them in an array. Ensure that the array is large enough, for now a size of 50 is good.

i) Make sure that you do not occur an out of bounds error on the array.

ii) You can convert the case of the names in the file as soon as you read it and store it in an array.
4. Your program should call a function that uses the Linear Search algorithm to locate the search item.

i) Make sure you make your comparisons case insensitive. That is, convert the user entered name to upper case for the assignment (converting to lower case will also result the same but I am testing with upper case values) before any comparison.

ii) Your function should keep a count of the number of comparisons it makes until it finds the value or reaches the end of the array.
5. Your program should then 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.
6. Display the number of comparisons that both the algorithms make.

Hints:

• Even though, for now the 'names.txt' only contains first names, don't forget to use getline() to read the names both from the file and from the standard input device.
• getline(inFile, name) will read from the file you opened and attached to inFile and store the result in the string variable name. The string variable can be an array element as well.
• You can use the following code to convert the strings to all uppercase. Write a function convertToUpperCase(string &) that takes a string value by reference and converts it to uppercase using the following code:

//string userInput contains the user's input or a name read from the file
for(int index = 0; index < userInput.length(); index++)
{
if(userInput[index] >= 'a' && userInput[index] <= 'z')
userInput[index] = toupper(userInput[index]);
}
cout << "uppercase is: " << userInput << endl;

• Other functions that you need to write should have the following prototypes:
  • int getFileInput(string [], int, string): the arguments are the string array, the size of the array and the user input (search item that you need to search for in the array).
  • int linearSearch(const string [], string, int, int &): the arguments are the string array, search item, the size of the array and the number of comparisons passed by reference.
  • int binarySearch(const string [], string, int, int &): the arguments are the string array, search item, the size of the array and the number of comparisons passed by reference.

Example 1: Your program should start by getting the file name from the user, followed by a name as user input.

Enter the file name: names.txt 
Enter name to search:

Let's say the user enters 'Sarah' as input then the output should be the following:

Enter name to search: Sarah

Using Linear Search, SARAH was found in the array in 32 comparisons.
Using Binary Search, SARAH was found in the array in 9 comparisons.

Example 2:

Enter name to search: Amy

Using Linear Search, AMY was found in the array in 2 comparisons.
Using Binary Search, AMY was found in the array in 9 comparisons.

Example 3:

Enter name to search: Virginia

Using Linear Search, VIRGINIA was found in the array in 35 comparisons.
Using Binary Search, VIRGINIA was found in the array in 13 comparisons.

Example 4:
If at any time the user enters a file name that doesn't exist, or your program is unable to open the file, you should display an error message. For example, if input.txt file doesn't exist, the output should be the following.

Enter file name: input.txt
Error!! Could not open file!

Answer 1

Program:

#include<iostream>
#include<fstream>
#include<string>

using namespace std;

//Function to convert the strings to all uppercase
void convertToUpperCase(string &str)
{
for(int i=0; i<str.size(); i++)
{
if(islower(str[i]))
str[i] = toupper(str[i]);
}
}

//Function to read the names from the file
void getFileInput(string nameArray[], int &n, string fname)
{
ifstream ifs;
ifs.open(fname.c_str());

if(!ifs){
cout<<"Error! Could not open file!";
exit(1);
}

for(n=0; getline(ifs, nameArray[n]) ; n++)
{
convertToUpperCase(nameArray[n]);
}
}

//Function to search a name using linear searching
void linearSearch(const string nameArray[], string name, int n, int &com)
{
for(com=0; com<n; com++){
if(nameArray[com]==name)
break;
}
com++;
if(com==n+1) com = -1;
}

//Function to search a name using binary searching
void binarySearch(const string nameArray[], string name, int n, int &com)
{
int i=0, j=n-1;
com = 0;

while(i<=j)
{
int mid = (i+j)/2;
com++;
if(nameArray[mid]==name)
return;
if(nameArray[mid]>name)
j=mid-1;
else
i=mid+1;
}
}

//main function
int main()
{
string fname, name, nameArray[50];
int n, m;

cout<<"Enter a file name: ";
cin>>fname;

getFileInput(nameArray, n, fname);

cin.ignore();

cout<<"Enter name to search: ";
getline(cin, name);

convertToUpperCase(name);

linearSearch(nameArray, name, n, m);

if(m==-1)
{
cout<< "Error: Not found!" <<endl;
return 0;
}

cout<<"Using linear search, " << name << " was found in the array in " << m << " comparisons." <<endl;

binarySearch(nameArray, name, n, m);

cout<<"Using binary search, " << name << " was found in the array in " << m << " comparisons." <<endl;

return 0;
}

names.txt

Al Clark
Angela Klein
Ashton Willams
Jerry Smith
Joan Garcia
Joyce Itin
Leslie McHenry
Mark Armstrong
Mary Jones
Melody Jung
Morgan Stock
Nick Lee
Robert Innes
Vahid Hamidi
Vera Moroz

Output:

Run1:

Enter a file name: name.txt
Error! Could not open file!

Run2:

Enter a file name: names.txt
Enter name to search: susan
Error: Not found!

Run3:

Enter a file name: names.txt
Enter name to search: nick lee
Using linear search, NICK LEE was found in the array in 12 comparisons.
Using binary search, NICK LEE was found in the array in 2 comparisons.