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

Question

структура данных для хранения начальной и конечной точки диапазона.

rangename      start     end

range1          10        11

range2          20        22

range3          0         5

Теперь, если мне нужно найти диапазон, в котором может существовать число 'x'.

Каков эффективный способ хранения этого в c ++?

Я пытаюсь использовать карту. но тогда поиск, чтобы найти диапазон, может быть дорогим (в чем я не уверен). Предложить хорошую структуру данных.

Я должен быть в состоянии найти, присутствует ли элемент в диапазоне или нет. Диапазоны не должны смешиваться и совмещаться, не должно быть смежных или иных границ.

Если мне нужно найти элемент 3, он присутствует в диапазоне 3, но элемент 12 отсутствует вообще. Простой цикл не может быть эффективным способом.

Answer 1

(Я изменил этот ответ, так как спрашивающий уточнил, что его диапазоны не перекрываются.)

Если набор диапазонов не изменяется, вы можете использовать отсортированный вектор и двоичный поиск, как предложено в ravenspoint.ответ.

Если набор диапазонов изменяется со временем, вы все равно можете использовать отсортированный вектор или вы можете использовать std::map.Вам нужно попробовать оба варианта и посмотреть, какой из них быстрее в этом случае.

Answer 2

vector< pair< int>> сохранено отсортировано, так что вы можете двоичный поиск, возможно?

Answer 3

Предполагая, что диапазоны не перекрываются:

Храните каждый диапазон в простой структуре

range {
  int low;
  int high;
  string name;
}

Сохранение диапазонов в отсортированном векторе, по низким значениям.

Найдите необходимый диапазон, используя бинарный поиск для наибольшего минимума, меньшего, чем цель.

Answer 4

почему бы не использовать дерево B +? При использовании дерева B + разветвление будет небольшим, и поиск будет также быстрым.

Answer 5

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

при условии, что вы получаете диапазоны из потока

vector<int> ranges;
int n;
while(in >> n){
    ranges.push_back(n);
}
sort(ranges.begin(),ranges.end())

int x;
cout <<"please enter a value to search for: ";
cin >> x;
int index = binary_search(x,ranges);

if(index % 2){
    cout << "The value " << x << "is in the range of "
         << ranges[index-1] << " to " <<       ranges[index] << endl;
}else{
    if(ranges[index] == x){
         cout << "The value " << x << "is in the range of "
              << ranges[index] << " to " <<       ranges[index+1] << endl;
    }
    else{
         cout << "Value " << x << " is not in any range\n";
    }
 }

, где двоичный поиск будет определен как

 int binary_search(int x, vector<int>& vec, int s = 0; int f = -1){
     if(f == -1)f=vec.size();
     if(s >= f) return s;
     int n = (f-s)/2 + s;
     if(vec[n] == x)return n;
     if(vec[n] < x)return binary_search(x,vec,s,n-1);
     return binary_search(x,vec,n+1,f);
 }

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