CKTIS / C++
Pesquisa linear
A pesquisa linear verifica elementos sucessivos sem exigir que os dados estejam ordenados. Em C++, std::find devolve um iterador para a primeira correspondência ou o iterador de fim.
Versão: C++23; repository compiler flag, production runtime not attested
Sintaxe
std::find(first, last, value)A pesquisa linear (linear search) verifica elementos sucessivos até encontrar uma correspondência ou esgotar o intervalo. Os dados não precisam de estar ordenados.
Use std::find(first, last, value) de <algorithm>. O intervalo [first, last) não inclui last. O resultado é um iterador para o primeiro elemento que satisfaz *it == value, não um índice. Se não houver correspondência, incluindo num intervalo vazio, o resultado é last; nunca o desreferencie.
Para n elementos, são necessárias no máximo n comparações: o custo no pior caso é O(n). O exemplo mostra duplicados e um valor que não existe. A subtração de iteradores dá um índice com base zero, porque std::array disponibiliza iteradores de acesso aleatório.
O exemplo destina-se a C++23. A página citada é um projeto em evolução, não uma publicação definitiva de C++23.
Exemplos
#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";
}
}
}
Resultado
3: index 1 7: not found
O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.