範囲の開始点と終了点を格納するためのデータ構造体である数字が

Question

の非重複範囲を見つけるための効率的なデータ構造。

rangename  start  end 

range1   10  11 

range2   20  22 

range3   0   5 

ここで、数字「x」が存在する可能性のある範囲を見つけなければならない場合は、

これをC++に格納する効率的な方法は何でしょうか？

私はマップを使用しようとしています。範囲を見つけるために検索するのは高価かもしれません（私は確信していません）。良いデータ構造を提案する。

要素が範囲内に存在するかどうかを調べることができます。範囲は混在していてはならず、隣接または他の境界はありません。

要素3を見つける必要がある場合、範囲3に存在しますが、要素12はまったく存在しません。ループするだけでは効率的な方法ではありません。

Answer 1

（アスカーは彼の範囲が重ならないことを明確にするので、私はこの答えを変更しました。）

範囲のセットが変更されない場合はravenspointの答えで提案されているように、あなたは、ソートされたベクトルとバイナリ検索を使用することができます。

時間の経過とともに一連の範囲が変更された場合でも、ソートベクターを使用する場合や、std::mapを使用する場合があります。あなたは両方を試し、どちらが速いかを見る必要があります。

ストア各範囲は、簡単な構造で

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

ストアソートベクトルに範囲を、低によって：範囲が重複しないと仮定すると

Answer 2

。

ターゲットが最も低いターゲットのうち、最も低いものに対してバイナリ検索を使用して必要な範囲を見つけます。

Answer 3

vector< pair< int>>おそらくバイナリ検索できるようにソートされていますか？

Answer 4

すべての値を開始し、終了してベクトルまたは配列にダンプしてから並べ替えます。範囲が重複しないので、配列がソートされると、開始、停止、開始、停止などが行われます。次に、バイナリ検索を使用してベクトルのインデックスを見つけることができます。そして、その問題だけかどうか、その奇数または偶数

を想定し、うまくいけば、私はdidnの、あなたはバイナリ検索が

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

として定義されるだろうストリーム

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

から範囲を取得しています」バイナリ検索を失敗させますが、値が見つからない場合は、次に大きい値のインデックスが返されるように設計されています。

Answer 5

なぜB +ツリーを使用しないのですか？ B +ツリーでは、ファンアウトが小さくなり、検索も高速になります。