WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

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.

Quellen