c++ - 显示所有匹配值的二进制搜索功能？

Question

我的作业要求我创建一个二进制搜索函数，该函数将搜索包含指定月份日期的结构数组，然后打印所有具有匹配月份的条目。

当我搜索多个值时，我很难让二分搜索正常工作，而且似乎无法弄清楚哪里出错了。

这是我的二进制搜索函数:

void binsearch(Event* ev_ptr[], int size, int month)
{
    int low = 0, high = size - 1, first_index = -1, last_index = -1;

    while (low <= high) //loop to find first occurence
    {
        int mid = (low + high) / 2;

        if (ev_ptr[mid]->date.month < month)
        {
            low = mid + 1;
        }
        else if (ev_ptr[mid]->date.month > month)
        {
            first_index = mid;
            high = mid - 1;
        }
        else if (ev_ptr[mid]->date.month == month)
        {
            low = mid + 1;
        }
    }

    low = 0; high = size - 1; //Reset so we can find the last occurence

    while (low <= high) //loop to find last occurence
    {
        int mid = (low + high) / 2;

        if (ev_ptr[mid]->date.month < month)
        {
            last_index = mid;
            low = mid + 1;
        }
        else if (ev_ptr[mid]->date.month > month)
        {
            high = mid - 1;
        }
        else if (ev_ptr[mid]->date.month == month)
        {
            high = mid + 1;
        }
    }

    for (int i = first_index; i <= last_index; i++)
    {
        cout << "\nEntry found: "
            << endl << ev_ptr[i]->desc
            << endl << "Date: " << ev_ptr[i]->date.month << '/' << ev_ptr[i]->date.day << '/' << ev_ptr[i]->date.year
            << endl << "Time: " << setw(2) << setfill('0') << ev_ptr[i]->time.hour << ':' << setw(2) << setfill('0') << ev_ptr[i]->time.minute << endl;
    }
}

这是我的主要功能:

const int MAX = 50;

int main()
{
    Event* event_pointers[MAX];
    int count, userMonth;
    char userString[80];

    count = readEvents(event_pointers, MAX);

    sort_desc(event_pointers, count);
    display(event_pointers, count);

    cout << "\n\nEnter a search string: ";
    cin.getline(userString, 80, '\n');
    cin.ignore();

    linsearch(event_pointers, count, userString);

    sort_date(event_pointers, count);
    display(event_pointers, count);

    cout << "\n\nEnter a month to list Events for: ";
    cin >> userMonth;
    cin.ignore();

    binsearch(event_pointers, count, userMonth);

    for (int j = 0; j < count; j++) //Cleanup loop
        delete event_pointers[j];

    cout << "\nPress any key to continue...";
    (void)_getch();
    return 0;
}

我已经完成了这项作业所需的所有其他工作，但似乎只是这种二分查找导致了问题。我尝试使用在最近一次迭代中在网上找到的一些东西(我在上面发布的内容)，但无济于事。任何帮助将不胜感激!

Answer 1

不要使用 binsearch 设置这些索引。搜索事件而不是向下和向上循环，直到条件失败。有点像

else if (ev_ptr[mid]->date.month == month)
{
            // mid = some occurence found 
            // increment and decrement mid until condition fails
}```