How to get if in which interval an index exists using set<pair<int, int>>

Question

I have std::set<std::pair<int, int>> intervals which it's values are some intervals, it is somthing similar to this:

{ 0, 5 },
{ 5, 8 },
{ 8, 10 }

and I have a number x can I find in which interval it is using lower_bound or upper_bound?

I need a solution with O(log(N)) complexity.

Because I remember that I saw someone doing it someway like this:

int x;
std::set<std::pair<int, int>> intervals;
cin >> x;
auto ans = intervals.upper_bound({ x, INF })

and I don't remember what was the value of INF

Note: the intervals aren't intersecting.

Answer 1

First of all, if you want to have a set of continuous ranges, you should simply represent them as a set that keeps only the beginning of each range.

set<int> boundaries { 0, 5, 8, 10 };

If you really want to use a structure that keeps both ends of a range, the following will allow you to search in O(log(N)). In the case of keeping both ends, it is possible to express other than continuous ranges set, so this example intentionally omits [6, 8). If the structure keeps both ends, it is also possible to express overlapping ranges set. In that case, we would have to search for more than one range. I left that example out.

#include <algorithm>
#include <limits>
#include <numeric>
#include <set>

using namespace std;
int main()
{
    set<pair<int, int>> intervals{ { 0, 5 },
                                   { 5, 6 },
                                   { 8, 10 } }; // drop {6, 8} version.
    {
        constexpr auto INF = numeric_limits<int>::max();
        auto find = [&](const int x) {
            auto next = intervals.upper_bound({ x, INF });
            if (next != intervals.begin()) {
                if (auto ans = prev(next); x < ans->second)
                    return ans;
            }
            return intervals.end();
        };
        for (int x = -1; x <= 11; ++x) {
            if (auto ans = find(x); ans != intervals.end()) {
                printf("%d is in [%d, %d)\n", x, ans->first, ans->second);
            } else {
                printf("%d is not in any range\n", x);
            }
        }
    }

    set<int> boundaries{ 0, 5, 8, 10 };
    {
        auto find = [&](const int x) {
            auto next = boundaries.upper_bound(x);
            if (next != boundaries.begin()) {
                return prev(next);
            }
            return boundaries.end();
        };

        for (int x = -1; x <= 11; ++x) {
            if (auto ans = find(x); ans != boundaries.end()) {
                if (auto nx = next(ans); nx != boundaries.end()) {
                    printf("%d is in [%d, %d)\n", x, *ans, *nx);
                } else {
                    printf("%d is in [%d, inf)\n", x, *ans);
                }
            } else {
                printf("%d is in [-inf, %d)\n", x, *boundaries.begin());
            }
        }
    }
}

stdout is here.

// == set<pair<int, int>>
-1 is not in any range
0 is in [0, 5)
1 is in [0, 5)
2 is in [0, 5)
3 is in [0, 5)
4 is in [0, 5)
5 is in [5, 6)
6 is not in any range
7 is not in any range
8 is in [8, 10)
9 is in [8, 10)
10 is not in any range
11 is not in any range

// == set<int>
-1 is in [-inf, 0)
0 is in [0, 5)
1 is in [0, 5)
2 is in [0, 5)
3 is in [0, 5)
4 is in [0, 5)
5 is in [5, 8)
6 is in [5, 8)
7 is in [5, 8)
8 is in [8, 10)
9 is in [8, 10)
10 is in [10, inf)
11 is in [10, inf)

Answer 2

Using the following method where the search range is specified as {x,x+1} we can get the required pair even when the pair ranges are a mix of overlapping and non-over-lapping ones in O(log(n)) using set.find() method. This uses a custom comparator.

#include <set>
#include <iostream>
#include <limits>

using namespace std;
typedef pair<int, int> Range;
struct RangeCompare
{
    bool operator()(const Range& lhv, const Range& rhv) const
    {
        return ((lhv.first <= lhv.second) && (lhv.first < rhv.first) && (lhv.second < rhv.second) && (rhv.first <= rhv.second));
    }
};


auto at_range(const set<Range, RangeCompare>& ranges, int value)
{
    return ranges.find(Range(value, value + 1)) ;
}

int main(int argc, char* argv[])
{
    if(argc < 2) {
      cout << "usage:<exe><search number>" << endl;
      exit(1);
    }
    //set<Range, RangeCompare> ranges = {{5,8},{11,14},{0,5},{8,11},{14,17},{20,23},{17,20},{6,8}};
    //set<Range, RangeCompare> ranges = {{5,8},{8,11},{11,14},{20,23},{40,51},{61,81}};
    set<Range, RangeCompare> ranges = {{5,10},{8,12},{10,14},{20,23},{40,51},{61,81}};

    int search = stoi(argv[1]);
    auto ret = at_range(ranges,search);
    if( ret != ranges.end())
      cout << ret->first << ' ' << ret->second <<'\n';
    else
      cout << "Value not found" << '\n';

    return 0;
}