CKTIS / C++
Lineární vyhledávání
Lineární vyhledávání postupně kontroluje prvky a nevyžaduje seřazená data. V C++ vrací std::find iterátor na první shodu, nebo koncový iterátor.
Verze: C++23; repository compiler flag, production runtime not attested
Syntaxe
std::find(first, last, value)Lineární vyhledávání (linear search) postupně kontroluje prvky, dokud nenajde shodu nebo nevyčerpá rozsah. Data nemusí být seřazená.
Použijte std::find(first, last, value) z <algorithm>. Rozsah [first, last) nezahrnuje last. Výsledkem je iterátor na první prvek, pro který platí *it == value, nikoli index. Pokud shoda neexistuje, a to i v prázdném rozsahu, výsledkem je last; tento iterátor nikdy nedereferencujte.
Pro n prvků je potřeba nejvýše n porovnání: složitost v nejhorším případě je O(n). Příklad ukazuje duplicitní hodnoty i chybějící hodnotu. Odečtením iterátorů získáte index počítaný od nuly, protože std::array poskytuje iterátory s náhodným přístupem.
Příklad je určen pro C++23. Citovaná stránka je průběžně vyvíjený pracovní návrh, nikoli neměnná publikace C++23.
Příklady
#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";
}
}
}
Výsledek
3: index 1 7: not found
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.