Expiring Today—Celebrate National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Binary Search

Posted on 2004-04-30
3
Medium Priority
?
573 Views
Last Modified: 2013-11-15
I am trying to do a binary search for the following program.  This program reads a txt file and sorts and outputs the student information by either grade, email, last name, or first name.  
Using binary search my program is supposed to ask the user to enter a student grade, once the user enters the grade the program outputs the closes student name with grade.  For example, if user enters 86 for the grade the program should output Alice Keith has grade of 84.6.  

The infile has this information:
Richard,Jones,richars@jones.com,78.5
Alice,Keith,alicek@yahoo.com,84.6
Diego,Salazar,ds@hotmail.com,91.2
Max,Karlov,max@kkk.org,63.2

Here is my program.
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

struct Student {
    string fname;
    string lname;
    string email;
    double grade;
};

Student* list[20];

int main1()
{
   
   
    fstream inFile("studentlist.txt");
    ofstream outFile;  //output file stream variable
      outFile.open("output10p1.txt"); //open outfile
   
      //declare variables
      char str[128];
    int i=0, c;            
   
    while (!inFile.eof())
    {
        inFile.getline(str, 128);
        string line = str;
        int pos1 = line.find(",");
        string fname = line.substr(0,pos1);
        int pos2 = line.find(",",pos1+1);
        string lname = line.substr(pos1+1,pos2-pos1-1);
        int pos3 = line.find(",",pos2+1);
        string email = line.substr(pos2+1,pos3-pos2-1);
        string grade = line.substr(pos3+1,line.length()-pos3-1);
        double grd = atof(grade.c_str());
         
        list[i] = new Student;
        list[i] ->fname = fname;
        list[i] ->lname = lname;
        list[i] ->email = email;
        list[i] ->grade = grd;
        i++;
   
    }
    // SAVE THE CURRENT VALUE OF THE LOOP COUNTER. IT'S THE STUDENTS COUNT
    int count = i;
                           
    // loop will keep function until user enters "0"
    while (true)
    {
        //(0 to quit)
        cout<<"Which column would you like to sort by (0 to quit) ==> "<<endl;
            cout<<"1) First Name"<<endl<<"2) Last Name"<<endl<<"3) Email"<<endl<<"4) Grade"<<endl;
        cin>>c;  
         
        // if "0" is entered loop will terminate
        if (c == 0)
            break;

        // Loop Runs Til Count == Number Of Students Read
        for (i=0; i < count; i++)
        {
            for (int j=i+1; j < count; j++)
            {
               
                switch (c)
                {
                case 1: if (list[i]->fname > list[j]->fname){
                    Student* tmp = list[i];
                    list[i] = list[j];
                    list[j] = tmp;
                    break;
                        }
                case 2: if (list[i]->lname > list[j]->lname){
                    Student* tmp = list[i];
                    list[i] = list[j];
                    list[j] = tmp;
                    break;
                        }
                case 3: if (list[i]->email > list[j]->email){
                    Student* tmp = list[i];
                    list[i] = list[j];
                    list[j] = tmp;
                    break;
                        }
                case 4: if (list[i]->grade > list[j]->grade){
                    Student* tmp = list[i];
                    list[i] = list[j];
                    list[j] = tmp;
                    break;
                        }
                   
                }
               
            }
           
        }
            cout <<"+-----------+-------------+---------------------+--------------------+"<<endl;
        cout <<"|First Name |  Last Name  |      Email          |      Grade         |"<<endl;
            cout <<"+-----------+-------------+---------------------+--------------------+"<<endl;
            
            // statement to output sorted table
        for (i=0; i< count; i++)
        {
                  cout <<list[i]->fname<<"\t    |   "<<list[i]->lname<<"\t  |  "<<list[i]->email<<"\t|\t"<<
                         list[i]->grade <<"\t     |"<< endl;
        }
            cout <<"+-----------+-------------+---------------------+--------------------+"<<endl;
      

      }
    return 0;
}
 
0
Comment
Question by:Steve3164
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
3 Comments
 

Expert Comment

by:alexanderthegreat
ID: 10967062
would it not be better just to let the program only search for names.

0
 
LVL 9

Expert Comment

by:keteracel
ID: 10968592
looks very homeworky to me!

A binary search requires a binary tree so instead of the "Student* list[20];" (which is syntactically incorrect anyway!) you'll need to have a tree struct (or use the standard library) and a pointer to the head node. Then you'll need functions to add students and search for students.

Since it looks like you're using C++ you should make a binary tree class to do all this.

That's as much as I'm going to give you as it does look like homework to me...
0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 1000 total points
ID: 10973409
I did it for you, but you should have tried to do it yourself. So i made no comments to the (tested) solution and i'll give you two tasks:

1. Student* list[20];     That will crash if the file contains more than 20 students.
    Try to use a variables

       Students** list = new Students*[20];
       int  listSize = 20;

    where you allocate new memory if  count exceeds listSize and where the contents of the previous list got copied to the new list.

2. Add comments to the prog

Regards, Alex


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

#ifdef WIN32
#define max _cpp_max
#endif

using namespace std;

struct Student {
    string fname;
    string lname;
    string email;
    double grade;
};

Student* list[20];

void swap(Student*& ps1, Student*& ps2)
{
    Student* ps = ps1;
    ps1 = ps2;
    ps2 = ps;
}


bool isless (Student* ps1, Student* ps2, int column)
{  
    if (column == 4)
        return ps1->grade < ps2->grade;
    else if (column == 3)
        return ps1->email < ps2->email;
    else if (column == 2)
        return ps1->lname < ps2->lname;
    else /* if (column == 1) */
        return ps1->fname < ps2->fname;
}

void sort(Student** list, int count, int column)
{
    for (int i = 0; i < count; i++ )
    {
        for (int j = i +  1; j < count; j++ )
        {
            if ( isless( list[j], list[i], column ) )
                swap( list[i], list[j] );
        }
    }
}

int main ()
{
    fstream inFile("studentlist.txt");
   
    char   str[128];
    int    i=0, c, a;
    double g;
   
    while (!inFile.eof())
    {
        inFile.getline(str, 128);
        string line = str;
        cout << line <<endl;
        int pos1 = line.find(",");
        string fname = line.substr(0,pos1);
        int pos2 = line.find(",",pos1+1);
        string lname = line.substr(pos1+1,pos2-pos1-1);
        int pos3 = line.find(",",pos2+1);
        string email = line.substr(pos2+1,pos3-pos2-1);
        string grade = line.substr(pos3+1,line.length()-pos3-1);
        double grd = atof(grade.c_str());
        list[i] = new Student;
        list[i] ->fname = fname;
        list[i] ->lname = lname;
        list[i] ->email = email;
        list[i] ->grade = grd;
        i++;
   
    }
    int count = i;

    while (true)
    {
        cout << "What do you want to do next?" << endl << endl;
        cout << "1\tSort list\n2\tSearch list for closest grade" << endl << endl;
        cout<<"Enter action code (0 to quit) ==>";
        cin >> a;
        if (a == 0 || a > 2)
            break;
        switch (a)
        {
        case 1:
            while (true)
            {
                cout<<"Which column would you like to sort by (0 to quit) ==>";
                cin >> c;
                if (c == 0 || c > 4)
                    break;
               
                sort (list, count, c);
               
                for (i=0; i < count; i++)
                {
                    cout <<list[i]->fname<<"\t    |   "<<list[i]->lname<<"\t  |  "<<list[i]->email<<"\t|\t"<<
                        list[i]->grade <<"\t     |"<< endl;
                }
            }
            break;

        case 2:
            while (true)
            {
                cout<<"What is the grade you are searching for (0 to quit) ==>";
                cin >> g;
                if (g == 0.0)
                    break;

                // First, we sort by column 4
                sort(list, count, 4);

                int n  = 0;
                int nl = 0;
                int nu = count;

                while (nl < nu)
                {
                    n = (nl + nu) / 2;    // get the middle
                    if (list[n]->grade == g)
                    {
                        nl = n;
                        break;
                    }
                    else if (list[n]->grade < g)
                        nl = n + 1;
                    else
                        nu = n;
                }
                // now nl is the position where the given grade would be inserted to maintain sort order
                // check neighbors to get closest
                n = nl;
                if (nl > 0)
                {
                    if (nl == count)
                        n = nl - 1;
                    else if ((g - list[nl-1]->grade) < (list[nl]->grade - g))
                        n = nl - 1;
                    else
                        n = nl;
                }
                cout <<list[n]->fname<<"\t    |   "<<list[n]->lname<<"\t  |  "<<list[n]->email<<"\t|\t"<<
                    list[n]->grade <<"\t     |"<< endl;
                cout << "is closest to the given grade " << g << endl << endl;
            }
            break;
        }    
       
    }
    return 0;
}


0

Featured Post

Learn how to optimize MySQL for your business need

With the increasing importance of apps & networks in both business & personal interconnections, perfor. has become one of the key metrics of successful communication. This ebook is a hands-on business-case-driven guide to understanding MySQL query parameter tuning & database perf

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Healthcare organizations in the United States must adhere to the guidance of both the HIPAA (Health Insurance Portability and Accountability Act) and HITECH (Health Information Technology for Economic and Clinical Health Act) for securing and protec…
Are you an Exchange administrator employed with an organization? And, have you encountered a corrupt Exchange database due to which you are not able to open its EDB file. This article will explain all the steps to repair corrupt Exchange database.
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

719 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question