Schnell feststellen, ob Wert innerhalb eines von vielen Intervallen liegt
-
Hallo!
Ich habe eine recht große Liste von nicht überlappenden Intervallen, z.B.
[0, 12), [14, 15), [20, 400), [404, 405) ...Nun möchte ich effizient feststellen, ob ein Wert in einem dieser Intervalle liegt.
Da es sehr viele sind, wäre es nicht so gut, jedes Intervall durchzugehen und dann zu testen.
Die maximalen Werte, die von den Intervallen beschrieben werden, sind aber auch relativ groß, so dass eine einfache Tabelle (die für jede Zahl beinhaltet, ob sie drin liegt oder nicht) auch nicht in Frage kommt.Am besten wäre da wohl ein binärer Baum, oder?
Gibt es in der C++-Standardbibliothek/STL etwas, womit ich das realisieren könnte, oder muss ich das selbst schreiben?
Danke!
-
std::map ist wie n binärbaum
-
Intervalle sortieren und dann immer Mitte prüfen->(Links/Rechts davon), bis nur eins übrigbleibt.
-
binäre Suche dürfte schon der richtige Ansatz sein - ich würde die einzelnen Teilintervalle als int-Paar speichern und dann per lower_bound() das nächstkleinere Intervall zu einem Suchwert bestimmen:
typedef pair<int,int> intervall; vector<intervall> data;//mit Werten füllen intervall dummy = make_pair(target,target); /* lower_bound() findet das nächste Element, was kleiner/gleich dem Suchwert ist, also liegt der Suchwert schonmal zwischen pos->first und (pos+1)->first */ vector<intervall>::iterator pos=lower_bound(data.begin(),data.end(),dummy); return pos->second>target;
-
Vielen Dank.
Mit dem lower_bound funktioniert es prima.
