Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

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.

Fontes