c++ - 如何使用二进制搜索 C++ 从二维数组中输出数据？

Question

我正在执行的其中一个函数使用二进制搜索来查找具有 2 行和 12 列的二维数组。第一行是学生证，所以一共有 12 个学生。第二行是每个学生对应的 GPA。我坚持的部分是当用户输入要搜索的学生 ID 时，使用二进制搜索显示 2D 数组中 12 名学生之一的 GPA。我已经为二进制搜索想出了这个，但我认为当用户输入学生 ID 进行搜索时，它不会为学生显示相应的 GPA。任何帮助都会很棒!

        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;
        }

Answer 1

对于二进制搜索，您搜索的数据必须排序。在您的情况下，二维数组在传递给搜索之前必须按学生 ID 排序。

如果您的数组的定义是 [2][12]，那么当您执行 row = 2 时，您将超出二维数组的范围。 C++ 是基于 0 的索引。如果 ID 是第一行，您需要执行 row = 0。我在下面重写了您的代码并做了一些更改。

首先:我删除了 found 变量，因为它不是必需的(您可以只使用 low < high 和一个 break 语句)。

第二:修复了假设 ID 是第一行而 GPA 是第二行的越界索引。

第三种:传入id进行搜索。由于您有一个 double 组，我将传入的 ID 用于搜索一个 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;
      }
    }
}

编辑:我可能建议创建一个存储学生信息的对象数组，而不是二维数组。下面的类应该做的很好。

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;
     }
}