CODEWITHSUNDEEP
c++arrays
Mark
Mark

Reputation: 283

How to output data from a two dimensional array by using binary search C++?

One of the functions I am doing uses a binary search for a two dimensional array with 2 rows and 12 columns. The first row is for student IDs, so there are 12 students total. The second row has the corresponding GPA for each student. The part where I am stuck on is using the binary search to display the GPA for one of the 12 students from the 2D array when a user enters in a student ID to search for. I have come up with this for the binary search, but I don't think it will display the corresponding GPA for a student when a user enters in a student ID to search for. Any help would be awesome!

        void search(double avg[][COLUMNS])
        int number;      // number is the student ID the user entered already
        int first = 0,
        last = MAX - 1,
        mid,
        position = -1;
        int row = 2;
        bool found = false;

        while (!found && first <= last)
        {
            mid = (first + last) / 2;
            if (avg[row][mid] == number)
            {
                cout << "found at index " << mid << endl;
                found = true;
            }
            else if (avg[row][mid] > number)
                last = mid - 1;
            else
                first = mid + 1;
        }

Upvotes: 2

Views: 453

Answers (1)

Timothy Murphy
Timothy Murphy

Reputation: 1362

For binary search the data your searching on must be sorted. In your case the 2D array must be sorted by Student ID before you pass it to search.

If the deminsions of your array is [2][12] then when you do row = 2 you are going out of bounds for the 2D array. C++ is 0 based indexing. If the ID is the first row you'll need to do row = 0. I've rewritten your code below with a few changes.

First: I removed the found variable since it isn't necessary (you can just use low < high and a break statement).

Second: Fixed out of bounds indexing assuming ID is the first row and GPA is second.

Third: Passed in the id to search for. Since you have a double array, I made the passed in ID to search for a double.

void search(double students[][COLUMNS], double id){
    int low(0), high(COLUMNS);
    int ID(0), GPA(1);  // Row 1 is ID (index 0), Row 2 is GPA (index 1).

    while (low <= high){
      int mid = (low+high)/2;
      if (students[ID][mid] < id)
        low = mid;
      else if (students[ID][mid] > id)
        high = mid;
      else {
        cout << "Found at index " << mid << " with GPA: " 
             << students[GPA][mid] << endl;
        break;
      }
    }
}

Edit: I might suggest instead of a 2D array, create an array of objects that store the students information. The below class should do just fine.

class Student{
   public:
     int ID;
     double GPA;
     Student(int id = 0, double gpa = 4.0):ID(id),GPA(gpa){}
     bool operator < (const Student& s){
       return ID < s.ID;
     }
}

Upvotes: 1

Related Questions