在向量<向量<int>>中二分查找向量<int>

Question

我有一个向量events，它由事件向量组成，例如：

events = [[1,3,2],[2,4,3],[4,5,2],[10,20,8]]

其中events[i]是格式[startTime_i, endTime_i, value_i]（含）。所有事件都按这样的方式排序，即jth 事件出现在ith 之后，if startTime_j > startTime_i。

由于事件已排序，我想使用二分搜索 ( lower_bound()) 来找出当前事件之后我可以参加的下一个非重叠事件。

有朋友建议使用：

vector<int> v={events[i][1]+1,INT_MIN,INT_MIN};
auto nextOne=lower_bound(begin(events),end(events),v);

我不遵循将第二个和第三个值设置为INT_MIN上面的直觉。有人可以解释一下吗？如果我必须获得一个upper_bound()，我是否必须使用INT_MAX它？

谢谢你！

Answer 1

这在一定程度上取决于您的排序标准。

您提到唯一的标准是“if startTime_j > startTime_i”。因此，“Event”结构的比较运算符可能如下所示：

// Simple comparison operator
bool operator < (const Event& other) const { return startTime < other.startTime; }

仅以开始时间作为比较标准。在这种情况下，INT_MIN 和 INT_MIN 只是虚拟的。它们不会用于 的任何比较std::lower_bound。我想，这是因为“搜索事件”中的第一个参数。看着

events[i][1]+1,INT_MIN,INT_MIN

在这里，我们构建一个事件，其中包含“endTime”和“value”的一些虚拟值（INT_MIN），并且起始时间比结束时间大一events[i]

重复。这意味着：我们搜索下一个事件，其中“startTime”大于当前元素的“endTime”。

例如，如果当前元素是 1,3,2，那么结束时间是 3。因此，如果我们不想重叠，我们需要查找开始时间 >= 3+1 的某个元素。这将是 4,5,2。

这是相当直观的。而且，如前所述，INT_MIN 只是一个虚拟值。它不会被使用。

为了说明这是如何工作的，请查看并运行以下代码：

#include <iostream>
#include <vector>
#include <algorithm>

struct Event {
    int startTime{};
    int endTime{};
    int value{};

    // Simple comparison operator
    bool operator < (const Event& other) const { return startTime < other.startTime; }

    // Simple overwrite of inserter operator for easy output
    friend std::ostream& operator << (std::ostream& os, const Event& e) {
        return os << e.startTime << ' ' << e.endTime << ' ' << e.value;
    }
};

int main() {
    // Main Test data
    std::vector<Event> events{ {2,4,3}, {1,3,2},{10,20,8},{4,5,2}};
    std::cout << "\nOriginal:\n";  
    for (const Event& e : events) std::cout << e << '\n';

    // Sort, if not yet sorted
    std::sort(events.begin(), events.end());
    std::cout << "\nSorted:\n";
    for (const Event& e : events) std::cout << e << '\n';

    // For test purposes: Search the next none overlapping event for each event
    for (const Event& e : events) {

        // Build the search event. It shall not overlap. So the start time of the next
        // must be greater than the end time of this
        Event searchEvent = e;
        searchEvent.startTime = e.endTime + 1;

        // Now search the
        std::cout << "\n\nLooking for the next none overlapping element after: " << e << '\n';

        std::vector<Event>::iterator next = std::lower_bound(events.begin(), events.end(), searchEvent);
        if (next != events.end()) {
            std::cout << "Found at index " << std::distance(events.begin(), next) << "   --> " << *next << '\n';
        }
        else std::cerr << "Not found\n";
    }
}