Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

Linearno pretraživanje

Linearno pretraživanje provjerava uzastopne elemente bez zahtjeva da podaci budu sortirani. U C++ std::find vraća iterator na prvo podudaranje ili završni iterator.

Verzija: C++23; repository compiler flag, production runtime not attested

Sintaksa

std::find(first, last, value)

Linearno pretraživanje (linear search) provjerava uzastopne elemente dok ne pronađe podudaranje ili ne iscrpi raspon. Podaci ne moraju biti sortirani.

Upotrijebite std::find(first, last, value) iz <algorithm>. Raspon [first, last) ne uključuje last. Rezultat je iterator na prvi element za koji vrijedi *it == value, a ne indeks. Ako nema podudaranja, uključujući i prazan raspon, rezultat je last; nemojte ga dereferencirati.

Za n elemenata potrebno je najviše n usporedbi: složenost u najgorem slučaju iznosi O(n). Primjer prikazuje duplikate i vrijednost koja nedostaje. Oduzimanjem iteratora dobiva se indeks koji počinje od nule jer std::array pruža iteratore s nasumičnim pristupom.

Primjer je namijenjen za C++23. Navedena stranica radni je nacrt koji se razvija, a ne nepromijenjena publikacija C++23.

Primjeri

#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

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori