CKTIS / C++
Lineair zoeken
Lineair zoeken controleert opeenvolgende elementen zonder dat de gegevens gesorteerd hoeven te zijn. In C++ geeft std::find een iterator naar de eerste overeenkomst of de einditerator terug.
Versie: C++23; repository compiler flag, production runtime not attested
Syntax
std::find(first, last, value)Lineair zoeken (linear search) controleert opeenvolgende elementen totdat een overeenkomst is gevonden of het bereik is doorlopen. De gegevens hoeven niet gesorteerd te zijn.
Gebruik std::find(first, last, value) uit <algorithm>. Het bereik [first, last) sluit last uit. Het resultaat is een iterator naar het eerste element waarvoor *it == value geldt, geen index. Als er geen overeenkomst is, ook bij een leeg bereik, is het resultaat last; dereferenceer deze iterator nooit.
Voor n elementen zijn hoogstens n vergelijkingen nodig: de kosten in het slechtste geval zijn O(n). Het voorbeeld laat duplicaten en een ontbrekende waarde zien. Door iterators van elkaar af te trekken krijg je een index die bij nul begint, omdat std::array iterators met willekeurige toegang biedt.
Het voorbeeld is bedoeld voor C++23. De genoemde pagina is een voortdurend bijgewerkt werkdocument, geen definitieve C++23-publicatie.
Voorbeelden
#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";
}
}
}
Resultaat
3: index 1 7: not found
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.