Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

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.

Zdroje