CKTIS / C++
Lineárne vyhľadávanie
Lineárne vyhľadávanie postupne kontroluje prvky bez toho, aby údaje museli byť zoradené. V C++ funkcia std::find vráti iterátor na prvú zhodu alebo koncový iterátor.
Verzia: C++23; repository compiler flag, production runtime not attested
Syntax
std::find(first, last, value)Lineárne vyhľadávanie (linear search) postupne kontroluje prvky, kým nenájde zhodu alebo nevyčerpá rozsah. Údaje nemusia byť zoradené.
Použite std::find(first, last, value) z <algorithm>. Rozsah [first, last) nezahŕňa last. Výsledkom je iterátor na prvý prvok, pre ktorý platí *it == value, nie index. Ak zhoda neexistuje, a to aj v prázdnom rozsahu, výsledkom je last; tento iterátor nikdy nedereferencujte.
Pre n prvkov treba najviac n porovnaní: zložitosť v najhoršom prípade je O(n). Príklad ukazuje duplicitné hodnoty aj chýbajúcu hodnotu. Odčítaním iterátorov získate index počítaný od nuly, pretože std::array poskytuje iterátory s náhodným prístupom.
Príklad je určený pre C++23. Citovaná stránka je priebežne vyvíjaný pracovný návrh, nie nemenná publikácia C++23.
Prí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ýsledok
3: index 1 7: not found
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.