I am writing a program that reads in names from a datafile and creates an array called students. I then sort this array using a selection sort. Then I need to prompt the user for a name and use a binary search to determine whether the name is in the array or not. If it is, I cout "yes the name is there...", if it is not, I cout "no, the name is not...".
I can read the datafile and populate the array. I can sort the array with the selection sort. I am having trouble with the binary search...every name I enter comes back as not in the array, even if it is.
I don't know if it makes a difference or not, but my array is sorting ascending ie. Z-A. I'm not sure why, or how to change it.
Here is the code:
Code:
#include <iostream>
#include <fstream>
#include <string>
int main()
{
const int max_students = 50;
const int exit = -1;
string students[max_students];
string in_name;
int num_students=0;
int i=0;
bool skipped_entry = false;
ifstream input("roster.dat");
// Check that file opens correctly
if(!input)
{
cout << "Cannot open datafile roster.dat. Bye!\n";
return(1);
}
// it doesn't read directly into the array
input >> in_name;
while(!input.eof())
{
if(num_students >= max_students)
{
skipped_entry = true;
break;
}
num_students++;
students[i] = in_name;
i++;
input >> in_name;
}
if(skipped_entry)
{
cout << "WARNING - Only " << max_students
<< " read in - rest ignored.\n";
}
else
{
cout << "Read in " << num_students
<< " names.\n";
}
cout << endl << "Here are the unsorted names from the roster.dat file: " << endl << endl;
for(i = 0; i < num_students; i++)
{
cout << "Student [" << i << "] is "
<< students[i] << endl;
}
// selection sort the array
int top = 0;
int largest;
string temp;
top = max_students;
i = 0;
for(top =0; top < (max_students -1); top++)
{
largest = top;
for (i = (top + 1); i < max_students; i++)
{
if (students[i] > students[largest])
largest = i;
}
// switch the 2 elements
temp = students[largest];
students[largest] = students[top];
students[top] = temp;
}
cout << endl << "Here are the sorted names from the roster.dat file: " << endl << endl;
for(i = 0; i < num_students; i++)
{
cout << "Student [" << i << "] is "
<< students[i] << endl;
}
// Binary search for a specific name in the roster.dat file
string input_name;
string check_name;
bool found = false;
int first = 0;
int last = num_students - 1;
int mid = (first + last) /2;
cout << endl << "Please enter a name to search for, or quit to exit: ";
cin >> input_name;
check_name = students[mid];
// This is the code that does the binary search
while (last >= first)
{
if (input_name == "quit")
{
cout << "Bye.";
return (0);
}
mid = (first + last) /2;
check_name = students[mid];
if (check_name == input_name)
found = true;
else if (input_name < check_name)
first = mid + 1;
else
last = mid - 1;
}
if (!found)
{
cout << input_name << " is not currently enrolled in the Fall 2002 CSC160 class." << endl << endl;
cout << "Please enter another name, or quit to exit: ";
cin >> input_name;
return 0;
}
else
{
cout << endl << input_name << " is a student in the Fall 2002 CSC160 class. " << endl << endl;
cout << "Please enter another name, or quit to exit: ";
cin >> input_name;
return 0;
}
return 0;
}
Thanks for any help in advance.
Brian