binary search in an array

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

One solution is a set container. Otherwise if you want to keep yoru algorithm, then make use of class string overloaded comparision operators.

Kuphryn

Got a feeling your code will go into an endless loop if the binary search actually finds something. I.e.

Code:

if (check_name == input_name)
  found = true;

You don't do any thing to get out of the loop, so it will go around endlessly. Maybe you could change this to:

Code:

if (check_name == input_name)
{
  found = true;
  break;
}

Also there is a command in the c library, called bsearch. This will perform a binary search for you, but requires a comparison callback function.

-----------------------------
bsearch
Performs a binary search of a sorted array.

void *bsearch( const void *key, const void *base, size_t num, size_t width, int ( __cdecl *compare ) ( const void *elem1, const void *elem2 ) );
-----------------------------

>Otherwise if you want to keep yoru algorithm, then make use of class string overloaded comparision operators.

It appears that you are doing this already.

It doesn't matter how you sort your array, provided the comparisons are made consistently between your sort algorithm & binary search.

I would check your sort algorithm and ensure that it is sorting in the way your binary search expects.

Code:

while (last >= first && found == false)

would also solve ur problem..
as someone else said earlier you are in an endless loop... when the program finnally does find the name in the array.. it assigns

Code:

found = true

however when u go back to the while loop it will keep going..
because..
the result could be found and last can still equal first

the break; as someone noted earlier is a solution as well..
u might want to write your programs with functions.. honestly the program is a mess.. and trying to debug it is hectic... too many local variables that are unnecessary... plus during debugging i notice u had multiple code pieces that do the exact same thing but run back to back...
int mid = (first + last) /2;
check_name = students[mid];
not a big deal in your program but i would be careful in the future... :P

Thanks for the help. I have made the changes suggested and the program seems to be executing the binary search correctly.

However, I need to be able to enter a name to search, perform the search, cout the results and then start the whole search over again.

How can I do this without putting my cout statements within the while loop? Because if they are in the while loop it assumes that after the first search iteration, the name is not found.

Brian