A quick search to find active ranges

Question

I have a range of numbers (In reality let's say they are 1'000'000). Each range has a lower and an upper bound. I have used a sort (in reality quick sort) function to sort them.

Now given a point 0.3, I would like to find all the ranges which contain this number. I look for an efficient way to find these active ranges. I am not sure whether upper_bound and lower_bound are the correct solutions. Could anyone please help me completing this code?

P.S. assuming the array length is huge, I look for a method which uses the advantage of sorted vector.

P.S. The overlapped layers are in the range of 500. Not as big as 1'000'000.

P.S. Always, min <= max (if important).

#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;
}

I don't see how separate sorted vectors will help. It makes it trivial to find what ranges have a lower min and larger max, but not both; — kmdreko, Jan 18 '18 at 07:19
advice for algorithm decisions also depend heavily on your data and usage... is the selected value likely to cover many of the ranges? are you doing this operation 1 or relatively few times? If either of those cases it might be better to make a simple loop. — kmdreko, Jan 18 '18 at 07:28
@vu1p3n0x, The number of overlaps are estimated to be in the range of `500`. — ar2015, Jan 18 '18 at 07:37
@ar2015 If you are searching for a single point only, then you cannot go better than O(n), because you have to check each interval at least once. Sorting takes O(nlogn), so it is worse than a linear scan through the list of intervals. If you are searching for a large number of points, then it makes sense to try with interval tree or similar data structure. — Miljen Mikic, Jan 18 '18 at 08:40
@MiljenMikic, no, I will loop through it. Consider a 3D printer printing a CAD file. — ar2015, Jan 18 '18 at 08:51

DAle · Accepted Answer · 2018-01-18T07:50:22.557

4

You are ordering starting and ending points of the intervals independently. After that, you discard some intervals with a binary search, but then you need to find an intersection of remaining intervals from max_list and min_list. This is not a big improvement compared to a linear search.

The efficient solution is a bit harder. There is an interval tree data structure that is often used to solve this kind of problems. It has O(n*log(n)) complexity of tree creation, and O(log(n)+m) complexity of the query where m is a size of the result.

edited Jan 18 '18 at 07:50

answered Jan 18 '18 at 07:16

DAle

8,990
2
26
45

What is the big O? What library to implement? – ar2015 Jan 18 '18 at 07:33
@ar2015, There is a question https://stackoverflow.com/questions/5407814/c-interval-tree-implementation about c++ implementations. – DAle Jan 18 '18 at 07:44
@ar2015 Q: What is the big O? A: google "time complexity" – Jabberwocky Jan 18 '18 at 07:57
@MichaelWalz, meant what is the big O of this algorithm. – ar2015 Jan 19 '18 at 01:01

score -1 · Answer 2 · answered Jan 18 '18 at 07:15

-1

Lower and upper bound are the correct way to go. I am not sure what you are trying to do with min_list and max_list, I would figure out a sorting for the ranges themselves then search those directly.

answered Jan 18 '18 at 07:15

SoronelHaetir

14,104
1
12
23

A quick search to find active ranges

2 Answers2