用于查找包含数字的非重叠范围的高效数据结构

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

<代码>向量<对< int>> 存储已排序，以便您可以进行二分搜索？

Answer 3

假设范围不重叠：

将每个范围存储在一个简单的结构中

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

将范围存储在按低排序的向量中。

使用二分搜索查找小于目标的最大低点所需的范围。

Answer 4

只需将所有值（开始和结束）转储到向量或数组中，然后对其进行排序即可。由于范围不重叠，一旦数组排序，您将有开始、停止、开始、停止等。然后，您可以使用二分搜索来查找向量的索引。那么这只是一个奇数还是偶数的问题

假设，您从流中获取

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

希望我没有搞砸二分搜索，但它的设计方式是这样的，如果未找到该值，则返回下一个最大值的索引。

Answer 5

为什么不使用B+树呢？
使用B+树，扇出会很小，搜索也会很快。