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

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

Answer 2

要设计正确的二分搜索函数，不要试图猜测解决方案，很难猜对。使用循环不变量的方法。找到第一次出现的函数在标准库中叫做lower_bound，所以我们在这里也使用这个名字：

template<class It, typename T>
It lower_bound(It first, std::size_t size, const T& value);

让我们引入last变量：auto last = first + size。我们将寻找一个过渡点 pt，以便在 [first, pt) 范围内，所有元素都具有值 < value，在 [pt, last) 范围内，所有元素都具有值 >= value。让我们介绍两个具有循环不变量的迭代器（指针）left 和 right：

范围 [first, left) 中所有元素的值都为 < value,
范围 [right, last) 中所有元素的值都为 >= value。

这些范围代表到目前为止检查的元素。最初，left = first 和 right = last，因此两个范围都是空的。在每次迭代中，其中一个将被扩展。最后，left = right，所以整个范围 [first, last) 已经检查过了。根据上面的定义，可以得出 pt = right.

下面的算法实现了这个想法：

template<class It, typename T>
It lower_bound(const It first, const std::size_t size, const T& value) {
    const auto last = first + size;

    auto left = first;
    auto right = last;

    while (left < right) {
        const auto mid = left + (right - left) / 2;
        if (*mid < value)         // examined [first, left)
            left = mid + 1;
        else                      // examined [right, last)
            right = mid;
    }

    return right;
}

这里我们可以重用变量first和last来表示left和right。我不是为了澄清。

现在让我们来分析一下您的实现。我可以推断出以下循环不变量：

[first, low) - 所有元素的值都为 < value,
(high, last) - 所有元素的值都为 >= value.

这些是相同的不变量，right 被替换为 high + 1。 while 循环本身是正确的，但是条件可以重写为

if (*mid <= value)
    low = mid + 1;
else {
    first_index = mid;
    high = mid - 1;
}

坏了。在这种情况下，范围 [first, low) 将包含所有值为 <= value 的元素。这对应于upper_bound。比较应该是 <，而不是 <=。

你可以用同样的方法分析第二个循环。在该循环中，至少有一项 mid 的赋值不正确。

int mid = (low + high) / 2;
...
    high = mid + 1;
...

这可能是一个无限循环。如果 high = low + 1，则 mid = low，并且您将 high 设置为 mid + 1 = high。您既不修改 low，也不修改 high，循环变成无限。

第一种方法，有两个半开范围是有益的 IMO。它是对称的，更容易推理。如果未找到任何值，则返回 last = first + size，这是表示范围结束的自然选择。您应该在循环后检查 first_index 和 last_index。如果他们没有被重新分配并且仍然保持 -1 怎么办？

Answer 3

1 将您的结构定义为此示例，

struct element {
  YourDate date;
  ...

  operator int() const { return  date.month;}
};

2 将元素排序为，

std::sort(elements.begin(), elements.end(), std::less<int>());

3 使用

std::equal_range(elements.begin(), elements.end(), your_target_month);

4 打印您从 std::equal_range

中得到的内容

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

Binary Search function that displays all matching values?

c++

function

freeze

binary-search