Busca sequencial simples e com sentinela

A busca sequencial (ou busca linear) é um dos primeiros problemas clássicos estudados em Algoritmos e Estruturas de Dados porque representa uma situação recorrente na vida dos programadores, que é tentar localizar uma informação dentro de uma coleção de dados. Em termos simples, buscar significa verificar se um valor está presente em uma sequência e, quando estiver, descobrir em qual posição ele aparece.

Segundo Cormen et al. (2024), a busca é um dos problemas fundamentais da computação, consistindo em determinar se um valor-alvo (chave de busca) está presente em um conjunto de dados e, em caso afirmativo, identificar sua posição. Em uma lista de notas, por exemplo, o programador pode querer descobrir se algum estudante obteve nota 10. Em um cadastro simples armazenado em array, pode ser necessário encontrar o código de um produto, o identificador de um cliente ou a matrícula de um aluno. Quando os dados estão desordenados, a estratégia mais direta é examinar os elementos um por um, do início ao fim. Essa é a essência da busca sequencial.

Neste artigo, serão estudadas duas formas de busca sequencial: a busca sequencial simples e a busca sequencial com sentinela. A primeira é a forma mais direta e didática, enquanto a segunda utiliza uma técnica clássica para reduzir uma verificação dentro do laço, tornando o algoritmo mais elegante em alguns contextos.

O que é busca sequencial?

O princípio da busca sequencial é, segundo Knuth (1998), o mais direto possível: percorrer os elementos do conjunto um a um, comparando cada um deles com a chave procurada, até que ocorra uma das duas condições de parada:

• o elemento é encontrado (sucesso); ou
• todos os elementos foram percorridos sem que a chave fosse localizada (fracasso).

Essa simplicidade é, ao mesmo tempo, sua maior virtude e sua maior limitação. Ela não exige nenhum pré-processamento nem estrutura de dados especial, mas também não se beneficia de qualquer conhecimento prévio sobre a organização dos dados.

Outra limitação considerável é o custo da solução com a busca sequencial. Por exemplo, se a sequência possui n elementos, o algoritmo pode precisar examinar apenas o primeiro elemento (caso ele seja o valor procurado) ou todos os elementos (caso o valor esteja na última posição ou não esteja presente). Por isso, na busca sequencial seu custo cresce proporcionalmente ao tamanho da entrada. Logo, entradas grandes podem fazer o custo computacional da busca ser muito alto.

O problema que a busca sequencial resolve

Imagine um sistema simples de controle de estoque. Cada produto possui um código inteiro, mas os produtos foram cadastrados na ordem em que chegaram ao sistema (ex: [120, 221, 401, 90, 305]). Nesse caso, os códigos não estão necessariamente ordenados. Caso o usuário queira encontrar o produto de código 305, o programa pode começar pela primeira posição do array, comparar o código armazenado com 305, avançar para a próxima posição e repetir esse processo até encontrar o produto ou confirmar que ele não está cadastrado.

Esse raciocínio é a base de muitos algoritmos mais sofisticados. Por isso, antes de estudar árvores, tabelas hash, índices de banco de dados ou busca binária, é importante que o estudante domine a lógica elementar de percorrer, comparar, parar e retornar uma resposta.

Busca sequencial simples

A busca sequencial simples usa duas condições principais dentro do laço. A primeira verifica se ainda há elementos a examinar. A segunda verifica se o elemento atual é igual ao valor procurado.

Em pseudocódigo, a ideia é:

comece na posição 0
enquanto a posição for válida:
    se o elemento atual for igual ao valor procurado:
        retorne a posição
    avance para a próxima posição
retorne -1

O retorno -1 é uma convenção comum para indicar que o elemento não foi encontrado, já que posições válidas de um array começam em 0.

A partir do pseudocódigo, podemos desenvolver uma proposta de algoritmo em linguagem C++. A versão abaixo é uma opção (disclaimer: não é a versão mais otimizada, mas entrega a solução desejada).

#include <iostream>

using namespace std;

int buscarSequencialSimples(int codigos[], int quantidade, int codigoProcurado) {
    for (int indice = 0; indice < quantidade; indice++) {
        if (codigos[indice] == codigoProcurado) {
            return indice;
        }
    }
    return -1;
}

int main() {
    int codigosProdutos[] = {101, 205, 150, 305, 220};
    int quantidade = 5, codigoProcurado = 305;

    int posicaoEncontrada = buscarSequencialSimples(codigosProdutos, quantidade, codigoProcurado);

    if (posicaoEncontrada != -1) {
        cout << "Produto encontrado na posição: " << posicaoEncontrada << endl;
    } else {
        cout << "Produto não encontrado." << endl;
    }
    return 0;
}

Nesse código, a função buscarSequencialSimples recebe um array de inteiros, a quantidade de elementos válidos e o código procurado. O laço for percorre o array da posição 0 até (quantidade - 1). A cada iteração, o algoritmo compara codigos[indice] com codigoProcurado. Se forem iguais, a função retorna imediatamente a posição encontrada.

Esse retorno imediato é importante, pois o algoritmo não precisa continuar procurando depois que encontrou o primeiro elemento correspondente. Caso nenhum elemento seja igual ao valor procurado, o laço termina e a função retorna -1.

Análise da busca sequencial simples

Como dissemos antes, o custo da busca sequencial simples cresce de acordo com a quantidade de dados na entrada. Considerando isso, podemos nos deparar com três cenários principais. No melhor caso, o valor procurado está na primeira posição, então o algoritmo faz apenas uma comparação. No pior caso, o valor está na última posição ou não está no array, obrigando o algoritmo a examinar todos os elementos. No caso médio, assumindo distribuição uniforme da posição do elemento, o algoritmo tende a examinar aproximadamente metade da coleção.

Dito isso, a Tabela 1 traduz as possibilidades, o números de comparações e a complexidade do algoritmo.

Para Cormen et al. (2024), o pior caso costuma ser uma referência importante para analisarmos a complexidade de algoritmos porque oferece um limite superior para o custo do algoritmo. No caso da busca sequencial, esse limite é linear, ou seja, dobrar a quantidade de elementos pode dobrar, aproximadamente, a quantidade de comparações no pior caso.

Para tentarmos otimizar (melhorar) o desempenho da busca sequencial simples, podemos introduzir a ideia de sentinelas.

O que é uma sentinela?

Uma sentinela (do inglês, sentinel) é um valor colocado propositalmente em uma posição estratégica da estrutura para simplificar a lógica de parada de um algoritmo. No caso da busca sequencial com sentinela, o valor procurado é colocado temporariamente no final da sequência. Assim, o laço sempre encontrará o valor em algum momento.

A ideia é basicamente sempre encontrar o valor desejado. Se o valor procurado já existir no array original, ele será encontrado antes da posição sentinela. Se não existir, o algoritmo chegará até a sentinela, indicando que o valor não estava entre os elementos reais.

Knuth (1998) discute técnicas desse tipo como formas de simplificar ou otimizar algoritmos de busca, especialmente por meio da redução de testes repetidos dentro de laços. A sentinela não muda a complexidade assintótica da busca, que continua sendo O(n), mas pode reduzir a quantidade de verificações feitas a cada iteração.

Busca sequencial com sentinela

Na busca sequencial simples, o laço costuma verificar duas coisas: 1) se o índice ainda está dentro do limite; e 2) se o elemento atual é o procurado. Como na versão com sentinela o valor procurado é colocado em uma posição adicional ao final do array, o laço não precisa verificar o limite a cada repetição, pois há garantia de que a busca encontrará o valor.

Porém, essa estratégia pede um cuidado na construção de estruturas estáticas como o array tradicional. Lembre-se que é necessário colocar uma posição extra disponível para armazenar a sentinela. Por exemplo, caso haja n elementos válidos, o array precisa ter capacidade para pelo menos n + 1 posições. Caso contrário, escrever a sentinela fora do array causaria acesso indevido à memória.

No algoritmo a seguir, refatoramos a lógica anterior para adicionar a sentinela no final do array e executar a buscar no conjunto de dados.

#include <iostream>

using namespace std;

int buscarSequencialComSentinela(int codigos[], int quantidade, int codigoProcurado) {
    codigos[quantidade] = codigoProcurado;
    int indice = 0;

    while (codigos[indice] != codigoProcurado) {
        indice++;
    }

    if (indice == quantidade) {
        return -1;
    }
    return indice;
}

int main() {
    const int CAPACIDADE = 6;
    int codigosProdutos[CAPACIDADE] = {101, 205, 150, 305, 220};
    int quantidade = 5, codigoProcurado = 305;

    int posicaoEncontrada = buscarSequencialComSentinela(codigosProdutos, quantidade, codigoProcurado);

    if (posicaoEncontrada != -1) {
        cout << "Produto encontrado na posição: " << posicaoEncontrada << endl;
    } else {
        cout << "Produto não encontrado." << endl;
    }
    return 0;
}

Observe que CAPACIDADE é igual a 6, mas quantidade é igual a 5. Isso significa que há cinco elementos reais no array e uma posição extra disponível para a sentinela. A linha codigos[quantidade] = codigoProcurado; grava o valor procurado exatamente na última posição após os dados válidos.

Se o valor 305 já estiver entre os produtos reais, o laço para antes da sentinela. Se o valor não estiver entre os produtos reais, o laço para na posição quantidade, que é a posição artificialmente preenchida. Por isso, depois do laço, a condição if (indice == quantidade) indica que o valor encontrado foi apenas a sentinela e não um dado real.

Comparação entre busca simples e busca com sentinela

A busca sequencial simples é mais intuitiva e mais segura para iniciantes, pois não altera o array e não exige uma posição extra. A busca com sentinela é um pouco mais sofisticada, pois modifica temporariamente a estrutura de dados para simplificar a condição do laço.

A principal diferença não está na complexidade assintótica, pois ambas continuam lineares. Conforme podemos ver na Tabela 2, a diferença está mais na construção lógica do laço de repetição. A versão com sentinela remove a necessidade de testar indice < quantidade dentro da repetição, porque a sentinela garante que o valor será encontrado em algum ponto. Esse tipo de detalhe nos ajuda a perceber que algoritmos podem ser analisados também pela forma como organizam suas operações internas para além das respostas que produzem.

Exemplo com um cenário mais real

Retomando o cenário do backlog de filmes visto no artigo “Revisando Algoritmos e Técnicas de Programação“, vamos tentar realizar uma busca sequencial simples no array que contém dados do tipo Filme, que é a struct já conhecida. O início do código ficaria assim:

// bibliotecas necessárias
#include <iostream>
#include <string>

using namespace std;

// constante de auxílio
const int CAPACIDADE_MAXIMA = 100;

// Registro (struct) para armazenamento dos dados
struct Filme {
    string titulo;
    string genero;
    int anoLancamento;
    double notaPessoal;
    bool assistido;
};

Em nosso exemplo, o usuário vai digitar o nome do filme que ele deseja encontrar. A função que executa a lógica da busca sequencial simples vai percorrer o vetor do primeiro ao último elemento, comparando o campo de interesse (neste caso, titulo) com a chave informada pelo usuário.

Para isso, na linha 1 do código abaixo estamos criando o protótipo (ou assinatura) da função buscaSequencialSimples, que recebe 3 parâmetros. Da linha 3 em diante, a função main está encarregada de solicitar o título do filme ao usuário, capturá-lo e chamar a função de busca. Ao final, ela apresenta a saída ao usuário com o retorno da função buscaSequencialSimples.

int buscaSequencialSimples(Filme backlog[], int totalFilmes, const string& tituloBuscado);

int main() {
    Filme backlog[CAPACIDADE_MAXIMA] = {
        {"Duna", "Ficcao Cientifica", 2021, 9.5, true},
        {"O Poderoso Chefao", "Drama", 1972, 10.0, true},
        {"Interestelar", "Ficcao Cientifica", 2014, 9.8, true},
        {"Parasita", "Suspense", 2019, 9.2, false}
    };
    int totalFilmes = 4;

    string tituloProcurado;
    cout << "Digite o titulo do filme que deseja buscar: ";
    getline(cin, tituloProcurado);

    int posicao = buscaSequencialSimples(backlog, totalFilmes, tituloProcurado);

    if (posicao != -1) {
        cout << "Filme encontrado na posicao " << posicao << "!" << endl;
        cout << "Genero: " << backlog[posicao].genero << endl;
        cout << "Ano: " << backlog[posicao].anoLancamento << endl;
    } else {
        cout << "Filme nao encontrado no backlog." << endl;
    }

    return 0;
}

O código escrito na linha 16 acima chama a função cuja assinatura declaramos na primeira linha. Agora, cabe a nós criarmos a lógica da busca sequencial simples efetivamente. O trecho de código a seguir é nossa proposta de solução para a função buscaSequencialSimples que pode ser escrita após a função main.

int buscaSequencialSimples(Filme backlog[], int totalFilmes, const string& tituloBuscado) {
    for (int i = 0; i < totalFilmes; i++) {
        if (backlog[i].titulo == tituloBuscado) {
            return i; // retorn a posição encontrada para o filme desejado
        }
    }
    return -1; // caso o título não tenha sido encontrado, retorna -1
}

O exemplo que propomos é básico, mas mostra como a estratégia de busca sequencial pode ser aplicada para cenários que se aproximam de casos reais.

Caso você queria aprimorar a estratégia da busca sequencial com uma sentinela, podemos refatorar o código anterior. Primeiro, basta adicionar a função buscaSequencialComSentinela escrita abaixo depois da função buscaSequencialSimples.

int buscaSequencialComSentinela(Filme backlog[], int totalFilmes, const string& tituloBuscado) {
    // Copia a chave buscada para a posição seguinte ao último elemento válido
    backlog[totalFilmes].titulo = tituloBuscado;

    int i = 0;
    while (backlog[i].titulo != tituloBuscado) {
        i++;
    }

    // Se i for igual a totalFilmes, encontramos apenas a sentinela (não encontrado)
    if (i == totalFilmes) {
        return -1;
    }
    return i;
}

Em segundo lugar, modifique a código da função main para chamar a função com sentinela. Na linha 17 da função main, adicione a chamada abaixo e comente a linha 16 para tirar a chamada da função anterior (buscaSequencialSimples).

int posicao = buscaSequencialComSentinela(backlog, totalFilmes, tituloProcurado);

Por último, acrescente a assinatura da função buscaSequencialComSentinela a seguir na linha 2 (antes do início do main). Isso fará com que a nova função seja reconhecida pelo compilador da linguagem C++.

int buscaSequencialComSentinela(Filme backlog[], int totalFilmes, const string& tituloBuscado)

Compile novamente o algoritmo e execute-o. Se tudo der certo, de duas uma: ou ele vai retornar o índice do array onde está o título do filme ou o número -1 caso não encontre.

Para encerrar, faço questão de destacar como é sempre importante aprendermos as estratégias mais simples dos algoritmos primeiro antes de partirmos para algo mais elaborado. Conforme Sedgewick e Wayne (2013), embora a busca sequencial não seja competitiva em grandes volumes de dados quando comparada à busca binária ou às tabelas de dispersão, ela continua sendo a técnica mais indicada para pequenos conjuntos de dados ou vetores não ordenados, situações em que o custo de ordenar ou indexar os dados superaria o ganho obtido na busca.

Essa visão vai ao encontro da opinião de Sebesta (2018, apud Ascencio; Campos, 2012) que destaca que a escolha de um algoritmo de busca não deve ser guiada apenas por sua complexidade teórica, mas também pelo contexto de uso. No caso do nosso sistema de backlog de filmes, a busca sequencial é plenamente justificável por tratar-se de uma estrutura pequena, não ordenada por natureza e de baixa frequência de consultas em relação a outras operações do sistema, como inserção e atualização de status de “assistido”.

Além disso, o estudo da busca sequencial funciona como alicerce conceitual para dois tópicos subsequentes fundamentais na disciplina de estrutura de dados:

1. Busca binária, que exige um vetor ordenado e introduz a lógica de divisão do espaço de busca (Ziviani, 2011);
2. Estruturas de dispersão (hash tables), que buscam eliminar completamente a necessidade de comparação sequencial por meio de funções de mapeamento direto (Cormen et al., 2024).

Conclusão

A busca sequencial é uma técnica fundamental para a formação do estudante em Computação porque ensina a percorrer dados, comparar valores, controlar laços, trabalhar com índices e definir critérios de parada. Esses elementos aparecem em praticamente toda a programação imperativa, desde exercícios introdutórios até sistemas mais complexos.

A versão simples do algoritmo de busca explicita as duas perguntas centrais que devem ser tratadas pelo algoritmo:

1. Ainda há elementos a verificar?
2. O elemento atual é o procurado?

Dominar a busca sequencial prepara o caminho para assuntos posteriores, como busca binária, ordenação, tabelas hash, árvores e índices. Antes de usar estruturas mais poderosas, o programador precisa entender o problema elementar: encontrar informação de forma correta, controlada e analisável.

Obrigado pela leitura e bons estudos!

Referências

CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Algoritmos – Teoria e Prática. 4 ed. Cambridge: MIT Press, 2024.

KNUTH, Donald E. The art of computer programming: sorting and searching. 2nd ed. Boston: Addison-Wesley, 1998. v. 3.

SEDGEWICK, Robert; WAYNE, Kevin. Algorithms. 4 ed. Boston: Addison-Wesley, 2013.

ZIVIANI, Nívio. Projeto de Algoritmos: com implementações em Pascal e C. 3 ed. São Paulo: Cengage Learning, 2011.