CKTIS / C++
Lineare Suche
Die lineare Suche prüft aufeinanderfolgende Elemente, ohne dass die Daten sortiert sein müssen. In C++ gibt std::find einen Iterator auf den ersten Treffer oder den Enditerator zurück.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
std::find(first, last, value)Die lineare Suche (linear search) prüft aufeinanderfolgende Elemente, bis ein Treffer gefunden oder der Bereich vollständig durchsucht wurde. Die Daten müssen nicht sortiert sein.
Verwende std::find(first, last, value) aus <algorithm>. Der Bereich [first, last) schließt last nicht ein. Das Ergebnis ist ein Iterator auf das erste Element, für das *it == value gilt, kein Index. Gibt es keinen Treffer, auch bei einem leeren Bereich, wird last zurückgegeben; dieser Iterator darf nicht dereferenziert werden.
Für n Elemente sind höchstens n Vergleiche nötig: Der Aufwand im schlimmsten Fall beträgt O(n). Das Beispiel zeigt Duplikate und einen nicht vorhandenen Wert. Durch Subtraktion von Iteratoren erhält man einen bei null beginnenden Index, da std::array Iteratoren mit wahlfreiem Zugriff bereitstellt.
Das Beispiel ist für C++23 vorgesehen. Die zitierte Seite ist ein fortlaufend bearbeiteter Entwurf und keine unveränderliche C++23-Veröffentlichung.
Beispiele
#include <algorithm>
#include <array>
#include <iostream>
int main() {
const std::array<int, 5> values{8, 3, 6, 3, 9};
for (int target : {3, 7}) {
const auto it = std::find(values.begin(), values.end(), target);
std::cout << target << ": ";
if (it != values.end()) {
std::cout << "index " << (it - values.begin()) << '\n';
} else {
std::cout << "not found\n";
}
}
}
Ergebnis
3: index 1 7: not found
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.