Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C++

Linearno iskanje

Linearno iskanje preverja zaporedne elemente, ne da bi morali biti podatki urejeni. V C++ std::find vrne iterator do prvega zadetka ali končni iterator.

Različica: C++23; repository compiler flag, production runtime not attested

Sintaksa

std::find(first, last, value)

Linearno iskanje (linear search) preverja zaporedne elemente, dokler ne najde zadetka ali izčrpa območja. Podatkov ni treba urediti.

Uporabite std::find(first, last, value) iz <algorithm>. Območje [first, last) ne vključuje last. Rezultat je iterator do prvega elementa, za katerega velja *it == value, ne indeks. Če zadetka ni, tudi v praznem območju, je rezultat last; tega iteratorja nikoli ne dereferencirajte.

Za n elementov je potrebnih največ n primerjav: najslabša časovna zahtevnost je O(n). Primer prikaže podvojene vrednosti in manjkajočo vrednost. Z odštevanjem iteratorjev dobimo indeks, ki se začne z nič, saj std::array zagotavlja iteratorje z naključnim dostopom.

Primer je namenjen C++23. Navedena stran je razvijajoči se delovni osnutek, ne nespremenjena izdaja C++23.

Primeri

#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";
        }
    }
}

Rezultat

3: index 1
7: not found

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri