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.