用於查找包含數字的非重疊範圍的高效數據結構

用於存儲範圍的起始和終點的數據結構。用於查找包含數字的非重疊範圍的高效數據結構

rangename  start  end 

range1   10  11 

range2   20  22 

range3   0   5

現在，如果我必須找到一個數字'x'的範圍可能存在。

什麼將這種存儲在c + +的有效方式？

我正在嘗試使用地圖。但後來搜索發現範圍可能是昂貴的（我不知道）。建議一個好的數據結構。

我應該能夠找到元素是否存在於一個範圍內。範圍不應該混合和匹配，也不得有相鄰或其他邊界。

如果我需要查找元素3，它出現在範圍3中，但元素12根本不存在。循環通過不是一種有效的方式。

來源

2011-12-14 King

你的範圍重疊嗎？查找任何特定數字的範圍是否會產生唯一的答案？ – ravenspoint 2011-12-14 21:28:05

範圍可以重疊嗎？ – 2011-12-14 21:28:25

你會有多少個範圍？他們多久更換一次？總人口數值有多大（即最大值 - 最小值）？ – 2011-12-14 21:32:46

（因爲提問者澄清說，他的範圍不重疊，我已經改變了這個答案。）

如果設置的範圍不會改變，你可以使用一個排序的矢量和二進制搜索，如ravenspoint的答案建議。

如果一組範圍隨時間變化，您仍可能使用排序向量，或者您可能想要使用std::map。您需要嘗試兩種方法，並在這種情況下查看哪一個更快。

來源

2011-12-14 21:27:51

假設範圍不重疊：

商店的每個範圍中的簡單結構

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

存放在排序的矢量範圍，由低。

使用二進制搜索來查找所需範圍最大的低於目標的最小值。

來源

2011-12-14 21:34:52 ravenspoint

vector< pair< int>>存儲排序，所以你可以二進制搜索？

來源

2011-12-14 22:16:55

只是轉儲所有的值，開始和結束到一個向量或數組，然後對其進行排序。因爲範圍不重疊，所以一旦數組被排序，就會有開始，停止，開始，停止等等。然後，可以使用二進制搜索來查找向量的索引。那麼它只是一個問題，即是否它的奇數或偶數

假設，你是從流

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

越來越範圍但願我沒有」 t搞砸了二分查找，但它的設計方式是，如果找不到該值，則返回下一個最大值的索引。

來源

2011-12-15 01:16:22 Smartelf

爲什麼不使用B +樹？有了B +樹，扇出會很小，搜索也會很快。

來源

2011-12-15 10:40:45

用於查找包含數字的非重疊範圍的高效數據結構

回答

相關問題