Ich verstehe, dass diese Aufgabe mit der Funktion find_if () STL-Algorithm wie folgt durchgeführt werden kann:
%Vor%Allerdings muss das Ergebnis in logarithmischer Zeit erhalten werden. Da der Vektor bereits in absteigender Reihenfolge sortiert ist, möchte ich einen binären Suchansatz verwenden.
Ich verstehe, dass die STL-Algorithmusfunktion lower_bound und upper_bound eine logarithmische Komplexität garantiert. Ich bin jedoch nicht in der Lage, herauszufinden, wie diese Funktionen verwendet werden, um das erste Element weniger als einen Schlüssel zu erhalten, im Gegensatz zu dem ersten Element, das größer oder gleich einem Schlüssel ist.
Zum Beispiel:
Angenommen, mein Vektorinhalt ist: 21 9 8 7 6 4
Mein Schlüssel ist: 10
Ich möchte, dass die Ausgabe 9 ist, da es das erste Element in einem Scan von links nach rechts des Vektors ist, der kleiner ist als 10 .
Jede Hilfe in dieser Hinsicht wäre sehr hilfreich!
Danke
Sie können den Standardalgorithmus std::upper_bound mit dem funktionalen Objekt std::greater verwenden.
Hier ist ein Beispiel, wie es gemacht werden kann.
%Vor%Die Programmausgabe ist
%Vor%