Thread: binary search in an array

  1. #1
    Registered User brianptodd's Avatar
    Join Date
    Oct 2002
    Posts
    66

    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

  2. #2
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    One solution is a set container. Otherwise if you want to keep yoru algorithm, then make use of class string overloaded comparision operators.

    Kuphryn

  3. #3
    Code Monkey Davros's Avatar
    Join Date
    Jun 2002
    Posts
    812
    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.

  4. #4
    Registered User
    Join Date
    Feb 2002
    Posts
    93

    interesting

    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
    Last edited by tegwin; 11-12-2002 at 01:43 PM.

  5. #5
    Registered User brianptodd's Avatar
    Join Date
    Oct 2002
    Posts
    66

    working now...almost

    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linear search for structure (record) array
    By jereland in forum C Programming
    Replies: 3
    Last Post: 04-21-2004, 07:31 AM
  2. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  3. Binary Search in C help
    By kce9751 in forum C Programming
    Replies: 2
    Last Post: 06-17-2003, 08:17 AM
  4. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM