Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

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.

Zdroje