在向量<int><向量中二进制搜索向量<int>>

Question

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

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

其中CCD_ 2的格式为CCD_。所有事件都以这样的方式排序，即如果startTime_j > startTime_i，则第j个事件出现在第i个事件之后。

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

一位朋友建议使用：

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

我不遵循上面将第2个和第3个值设置为INT_MIN的直觉。有人能解释一下吗？如果我必须使用upper_bound()，我会使用INT_MAX吗？

谢谢！

Answer 1

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

你提到唯一的准则是"；如果startTime_j>startTime_i"；。因此，您的"；事件"；结构可能类似于：

// 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

在这里，我们构建一个事件，该事件具有用于"事件"的一些伪值(INT_MIN(；endTime"；以及"；值"；并且具有比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 << "nnLooking 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 foundn";
}
}