c++ - 快速搜索以查找事件范围

Question

我有一个数字范围(实际上假设它们是 1'000'000)。每个范围都有一个下限和一个上限。我使用了排序(实际上是快速排序)函数来对它们进行排序。

现在给出一个点0.3 ，我想找到包含该数字的所有范围。我寻找一种有效的方法来找到这些活跃范围。我不确定是否upper_bound和 lower_bound是正确的解决方案。谁能帮我完成这段代码吗？

附注假设数组长度很大，我寻找一种利用排序 vector 优势的方法。

附注重叠层的范围为 500 。没有1'000'000那么大.

附注永远，min <= max (如果重要的话)。

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

class Range
{
public:
    double min;
    double max;
};

int main()
{
    std::vector<Range> range_list
        {
            {0.020742,0.460304},
            {0.168229,0.274032},
            {0.174609,0.420922},
            {0.352116,0.660738},
            {0.445867,0.910085},
            {0.249047,0.794357},
            {0.264342,0.953567},
            {0.671572,0.823919},
            {0.424151,0.891832},
            {0.041007,0.515920}
        };
    std::vector<int> min_list;
    std::vector<int> max_list;
    min_list.resize(range_list.size());
    for(int i=0;i<(int)range_list.size();i++)
        min_list[i]=i;
    max_list=min_list;
    std::sort(
        min_list.begin(),
        min_list.end(),
        [&range_list](int i,int j)
        {
            return range_list[i].min<range_list[j].min;
        });
    std::sort(
        max_list.begin(),
        max_list.end(),
        [&range_list](int i,int j)
        {
            return range_list[i].max<range_list[j].max;
        });

    std::vector<int>::iterator ???,???;
    ???=std::lower_bound(min_list.begin(),
            range_list.end(), 0.3);
    ???= std::upper_bound(max_list.begin(),
            range_list.end(), 0.3);
    ????????????

    std::vector<int> active_range=...

    std::cout<<"Active ranges are:"<<std::endl;
    for(auto x: active_range)
        std::cout<<"("<<x.min<<","<<x.max<<")"<<std::endl;

    return 0;
}

Answer 1

您正在独立排序间隔的起点和终点。之后，您通过二分搜索丢弃一些间隔，但随后您需要从 max_list 和 min_list 中找到剩余间隔的交集。与线性搜索相比，这并不是一个很大的改进。

有效的解决方案有点困难。有一个interval tree数据结构常用于解决此类问题。它的树创建复杂度为 O(n*log(n))，查询复杂度为 O(log(n)+m)，其中 m 是结果的大小。