快速搜索以查找活动范围

Question

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

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

P.S。假设数组长度很大，我寻找一种利用排序向量优势的方法。

P.S。重叠层数在500范围内。没有 1'000'000.

大

P.S。总是，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

下限和上限是正确的方法。我不确定你想用 min_list 和 max_list 做什么，我会想办法对范围本身进行排序，然后直接搜索它们。

Answer 2

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

有效的解决方案有点难。有一种interval tree数据结构经常被用来解决这类问题。它具有 O(n*log(n)) 树创建复杂度和 O(log(n)+m) 查询复杂度，其中 m 是结果的大小。

快速搜索以查找活动范围

A quick search to find active ranges

c++

algorithm

binary-search

c++11