Хранение набора неперекрывающихся диапазонов и нахождение, строго ли присутствует значение в любом из диапазонов

Question

У меня есть набор диапазонов:

Диапазон1 ---- (0-10)

Диапазон 2 ---- (15-25)

Range3 ---- (100-1000) и аналогично. Я хотел бы хранить только границы, так как при хранении больших диапазонов это будет эффективно.

Теперь мне нужно найти число, скажем, 14. В этом случае 14 не присутствует ни в одном из диапазонов, тогда как (скажем, число) 16 присутствует в одном из диапазонов.

Мне нужна функция

bool search(ranges, searchvalue)
{
    if searchvalues present in any of the ranges
        return true;
    else
        return false;
}

Как лучше всего это сделать? Это строго не совпадает, и важным критерием является то, что поиск должен быть наиболее эффективным.

Answer 1

Одной из возможностей является представление диапазонов в виде пары значений и определение подходящей функции сравнения.Следующее должно рассмотреть один диапазон меньше, чем другой, если его границы меньше и нет перекрытия.Как побочный эффект, эта функция сравнения не позволяет хранить перекрывающиеся диапазоны в наборе.

Чтобы найти целое число n, его можно рассматривать как диапазон [n, n]

#include <set>
#include <iostream>

typedef std::pair<int, int> Range;
struct RangeCompare
{
    //overlapping ranges are considered equivalent
    bool operator()(const Range& lhv, const Range& rhv) const
    {   
        return lhv.second < rhv.first;
    } 
};

bool in_range(const std::set<Range, RangeCompare>& ranges, int value)
{
    return ranges.find(Range(value, value)) != ranges.end();
}

int main()
{
    std::set<Range, RangeCompare> ranges;
    ranges.insert(Range(0, 10));
    ranges.insert(Range(15, 25));
    ranges.insert(Range(100, 1000));
    std::cout << in_range(ranges, 14) << ' ' << in_range(ranges, 16) << '\n';
}

Answer 2

Стандартный способ справиться с этим - через так называемые деревья интервалов .По существу, вы дополняете обычное красно-черное дерево дополнительной информацией, чтобы каждый узел x содержал интервал x.int, а ключ x - это нижняя конечная точка, x.int.low, интервала.Каждый узел x также содержит значение x.max, которое является максимальным значением любой конечной точки интервала, хранящейся в поддереве с корнем в x.Теперь вы можете определить x.max с заданным интервалом x.int и максимальными значениями дочерних узлов x следующим образом:

x.max = max (x.int.high, x.left.max, x.right.max)

Это означает, что с интервалами n вставка и удаление выполняются за время O (lg n ).Фактически, можно обновить атрибуты max после поворота за время O (1).Вот как искать элемент i в дереве интервалов T

INTERVAL-SEARCH(T, i)
x = T:root
while x is different from T.nil and i does not overlap x.int
   if x.left is different from T.nil and x.left.max is greater than or equal to i.low 
      x = x.left
  else 
      x = x.right 
return x

Сложность процедуры поиска также составляет O (lg n ).Чтобы понять почему, см. CLRS Введение в алгоритмы , глава 14 (Дополнение структур данных).

Answer 3

Вы можете собрать что-нибудь вместе на основе std::map и std::map::upper_bound:

Если у вас есть

std::map<int,int> ranges; // key is start of range, value is end of range

Вы можете сделать следующее:

bool search(const std::map<int,int>& ranges, int searchvalue)
{
    auto p = ranges.upper_bound(searchvalue); 
      // p->first > searchvalue
    if(p == ranges.begin())
        return false;
    --p;  // p->first <= searchvalue
    return searchvalue >= p->first && searchvalue <= p->second;
}

Я использую C ++ 11, если вы используете C ++ 03, вам нужно заменить «auto» на правильный тип итератора.

РЕДАКТИРОВАТЬ: заменил псевдокод inrange () явным выражением в операторе возврата.

Answer 4

Хорошим решением может быть следующее. Это O (log (n)).

Критическое состояние - это не перекрывающиеся диапазоны.

#include <set>
#include <iostream>
#include <assert.h>

template <typename T> struct z_range
{
        T s , e ;
        z_range ( T const & s,T const & e ) : s(s<=e?s:e), e(s<=e?e:s)
        {
        }
};

template <typename T> bool operator < (z_range<T> const & x , z_range<T> const & y )
{
    if ( x.e<y.s)
        return true ;
    return false ;
}

int main(int , char *[])
{
    std::set<z_range<int> > x;
    x.insert(z_range<int>(20,10));
    x.insert(z_range<int>(30,40));
    x.insert(z_range<int>(5,9));
    x.insert(z_range<int>(45,55));

    if (x.find(z_range<int>(15,15)) != x.end() )
        std::cout << "I have it" << std::endl ;
    else
        std::cout << "not exists" << std::endl ;

}

Answer 5

Если у вас есть диапазоны ri = [ai, bi]. Вы можете отсортировать все ai и поместить их в массив и найти x, имеющий x >= ai and ai minimal, используя бинарный поиск.

После того, как вы нашли этот элемент, вы должны проверить, является ли x <= bi.

Это подходит, если у вас большие цифры. С другой стороны, если у вас много памяти или небольшие числа, вы можете подумать о том, чтобы поместить эти диапазоны в массив bool. Это может подойти, если у вас много запросов:

bool ar[];
ar[0..10] = true;
ar[15..25] = true;
// ...

bool check(int searchValues) {
  return ar[searchValues];
}

Answer 6

Итак, предполагается, что диапазоны непрерывны (т. Е. Диапазон [100,1000] содержит все числа от 100 до 1000):

#include <iostream>
#include <map>
#include <algorithm>

bool is_in_ranges(std::map<int, int> ranges, int value)
{
    return
    std::find_if(ranges.begin(), ranges.end(),
        [&](std::pair<int,int> pair)
        {
             return value >= pair.first && value <= pair.second;
        }
    ) != ranges.end();
}

int main()
{
    std::map<int, int> ranges;
    ranges[0] = 10;
    ranges[15] = 25;
    ranges[100] = 1000;

    std::cout << is_in_ranges(ranges, 14) << '\n';  // 0
    std::cout << is_in_ranges(ranges, 16) << '\n';  // 1
}

В C ++ 03 вам понадобится функтор вместолямбда-функции:

struct is_in {
    is_in(int x) : value(x) {}
    bool operator()(std::pair<int, int> pair)
    {
        return value >= pair.first && value <= pair.second;
    }
private:
    int value;
};

bool is_in_ranges(std::map<int, int> ranges, int value)
{
    return
    std::find_if(ranges.begin(), ranges.end(), is_in(value)) != ranges.end();
}

Answer 7

Поскольку диапазоны не перекрываются, остается только выполнить поиск в пределах диапазона, который соответствует значению.Если значения упорядочены в пределах диапазонов, поиск еще проще. Здесь - сводка алгоритмов поиска.

Что касается C ++, вы также можете использовать алгоритмы из STL или даже функции, предоставляемые контейнерами, например, set::find.