一个数据结构,用于存储范围的起始点和端点。
rangename start end
range1 10 11
range2 20 22
range3 0 5
现在,如果我必须找到一个数字'x'可能存在的范围。
在c++中如何有效地存储它?
我正在尝试使用地图。但是搜索范围可能会很昂贵(我不确定)。建议一个好的数据结构。
我应该能够找到元素是否存在于一个范围内。范围不应混合和匹配,也没有相邻或其他边界。
如果我需要查找元素3,它在范围3中,但是元素12根本不存在。只是循环遍历并不是有效的方法。
(由于提问者澄清了他的范围不重叠,我已经更改了这个答案)
如果范围集没有改变,您可以使用排序向量和二进制搜索,如ravenpoint的答案所建议的。
如果范围集随时间变化,您可能仍然使用排序向量,或者您可能希望使用std::map
。您需要尝试两种方法,看看哪种方法在这种情况下更快。
vector< pair< int>>
存储排序,所以你可以二进制搜索也许?
假设范围不重叠:
将每个范围存储在一个简单的结构
中range {
int low;
int high;
string name;
}
将范围存储在一个有序的向量中,按low。
只是转储所有的值,开始和结束到一个向量或数组,然后排序。由于范围不重叠,一旦数组被排序,你将有start,stop, start,stop等等。然后,您可以使用二分搜索来查找向量的索引。那么问题就变成是奇数还是偶数了
假设您从流
获得范围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 rangen";
}
}
,其中二分查找将定义为
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);
}
希望我没有搞砸二进制搜索,但它的设计方式是,如果没有找到值,则返回下一个最大值的索引。
为什么不用B+树呢?使用B+树,扇形输出会很小,搜索也会很快。