Programação Tutorial , , , ,

Busca binária iterativa e recursiva

Suponha um catálogo de filmes ordenado por ano de lançamento. Neste cenário, como poderíamos localizar rapidamente uma obra específica sem percorrer item a item o conjunto de dados? Esse problema é bastante recorrente em bancos de dados, sistemas de arquivos, compiladores e estruturas de indexação e pode ser resolvido de forma elegante pela busca binária, um dos algoritmos mais estudados em Ciência da Computação por combinar simplicidade conceitual e eficiência assintótica notável.

Neste artigo vamos apresentar a busca binária em duas formulações — iterativa e recursiva —, discutir suas implementações em C++ sobre vetores estáticos ordenados, analisar formalmente sua complexidade e apontar armadilhas comuns de implementação. Manteremos, como fio condutor dos exemplos, um pequeno sistema de consulta a um acervo de filmes ordenado por ano de lançamento — cenário simples, mas suficiente para evidenciar cada aspecto do algoritmo.

O que é busca binária?

A busca binária é um algoritmo de pesquisa utilizado para localizar um valor em uma sequência previamente ordenada. Sua ideia central é comparar o valor procurado com o elemento central do vetor e, a partir dessa comparação, descartar metade dos elementos restantes, continuando a busca apenas na metade onde o valor ainda pode estar. Observe que essa lógica é contrária à busca sequencial, pois o algoritmo não vai verificar os elementos um por um em todo o conjunto de dados.

Podemos dizer também que o algoritmo é uma técnica de busca baseada na estratégia de divisão sucessiva do espaço de pesquisa. Dado um vetor ordenado, o algoritmo mantém dois limites: o início e o fim da região onde o valor pode estar. A cada passo, o algoritmo calcula a posição central dessa região e compara o elemento central com o valor procurado.

Se o elemento central for igual ao valor procurado, a busca termina. Se o valor procurado for menor que o elemento central, o algoritmo descarta a metade direita. Se for maior, descarta a metade esquerda. Segundo Martins (2009), esse processo continua até que o valor seja encontrado ou até que a região de busca se torne vazia, ou seja, até que o limite final torne-se menor que o limite inicial. Portanto, o encerramento da busca depende de duas condições: encontrar o valor ou esgotar o intervalo possível de pesquisa.

Pré-condição para a busca binária

A busca binária exige uma pré-condição indispensável para sua aplicação: o vetor precisa estar ordenado. Sem ordenação, não há garantia de que o valor menor esteja à esquerda nem de que o valor maior esteja à direita. Nesse caso, descartar metade do vetor pode eliminar exatamente a região onde o valor procurado se encontra.

Por exemplo, considere o vetor ordenado:

int codigos[] = {101, 203, 305, 410, 512, 608, 777};

Se procuramos o código 410, podemos comparar primeiro com o elemento central. Como o vetor está ordenado, cada decisão elimina uma parte do problema com segurança.

Agora considere um vetor desordenado:

int codigos[] = {410, 101, 777, 203, 512, 305, 608};

Nesse caso, a busca binária não é adequada, pois a posição relativa dos elementos não preserva uma ordem lógica. Antes de aplicar a busca binária, seria necessário ordenar o vetor ou escolher outro método de busca.

Intuição do algoritmo

Imagine uma lista telefônica impressa. Para encontrar um nome, dificilmente uma pessoa começa na primeira página e lê todos os nomes até chegar ao resultado. O procedimento natural é abrir a lista em uma região intermediária, verificar se o nome procurado viria antes ou depois daquela página e repetir o processo em uma parte menor da lista. A busca binária funciona de forma semelhante.

Basicamente, podemos resumir o princípio da busca binária em três passos, aplicados repetidamente sobre um intervalo [esquerda, direita] que representa a região do vetor ainda não descartada:

  1. Calcula-se o índice do elemento central do intervalo.
  2. Compara-se o valor buscado com o elemento central:
    • Se forem iguais, a busca termina com sucesso.
    • Se o valor buscado for menor, a busca prossegue na metade esquerda.
    • Se for maior, a busca prossegue na metade direita.
  3. O processo se repete até que o elemento seja encontrado ou o intervalo se torne vazio.

A execução desses três passos transforma a pesquisa em um processo de redução progressiva do intervalo de análise. Se o vetor possui 1.000 elementos, a primeira comparação pode reduzir o problema para aproximadamente 500 elementos. A segunda, para 250. A terceira, para 125. Esse comportamento explica sua eficiência.

Ziviani (2010) situa a busca binária como vantajosa à medida que o volume de dados cresce, justamente por evitar a varredura completa da estrutura. Em contrapartida, o autor alerta que a manutenção da ordenação tem custo — cada inserção em uma posição intermediária exige deslocar os registros subsequentes —, de modo que a busca binária não deve ser empregada em aplicações muito dinâmicas, isto é, com muitas inserções e remoções intercaladas com buscas (Ziviani, 2010).

Exemplo conceitual passo a passo

Considere o vetor:

Índice:  0    1    2    3    4    5    6
Valor:  10   20   30   40   50   60   70

Nesse conjunto, deseja-se procurar o valor 60. Na primeira iteração, o início é 0, o fim é 6 e o meio é 3. O valor na posição 3 é 40. Como 60 é maior que 40, a busca continua na metade direita.

Agora o início passa a ser 4, o fim continua 6 e o meio passa a ser 5. O valor na posição 5 é 60. Como o valor foi encontrado, o algoritmo retorna a posição 5.

Observe que o algoritmo encontrou o valor com apenas duas comparações. Uma busca sequencial, nesse mesmo caso, poderia exigir seis comparações se começasse no índice 0.

Com base no exemplo conceitual, podemos descrever a função de busca binária em forma de pseudocódigo assim:

FUNÇÃO buscaBinaria(vetor, tamanho, valorProcurado)
    inicio ← 0
    fim ← tamanho - 1

    ENQUANTO inicio <= fim FAÇA
        meio ← inicio + (fim - inicio) / 2

        SE vetor[meio] = valorProcurado ENTÃO
            RETORNE meio
        FIM SE

        SE valorProcurado < vetor[meio] ENTÃO
            fim ← meio - 1
        SENÃO
            inicio ← meio + 1
        FIM SE
    FIM ENQUANTO

    RETORNE -1
FIM FUNÇÃO

A lógica do pseudocódigo é começar considerando todo o vetor como área possível de busca. Em seguida, calcular a posição central. Se o valor central for o elemento procurado, retorna sua posição. Se o valor procurado for menor, continua apenas na metade esquerda. Se for maior, continua apenas na metade direita. Quando a variável inicio ultrapassar a variável fim, significa que não existe mais região válida para pesquisar e, por isso, a função retornará o valor -1.

Busca binária iterativa

Agora, vamos transformar a lógica da busca binária num código em linguagem C++. A primeira versão que demonstraremos é a iterativa, usando uma estrutura de repetição (geralmente while) para atualizar os limites da busca. Ela tende a ser a forma mais direta para iniciantes, pois deixa explícitas as mudanças nas variáveis inicio, fim e meio.

Leia e observe o algoritmo a seguir:

#include <iostream>

using namespace std;

int buscaBinariaIterativa(int dados[], int tamanho, int valorProcurado) {
    int inicio = 0;
    int fim = tamanho - 1;

    while (inicio <= fim) {
        int meio = inicio + (fim - inicio) / 2;

        if (dados[meio] == valorProcurado) {
            return meio;
        }

        if (valorProcurado < dados[meio]) {
            fim = meio - 1;
        } else {
            inicio = meio + 1;
        }
    }

    return -1;
}

int main() {
    int codigos[] = {101, 203, 305, 410, 512, 608, 777};
    int tamanho = 7;
    int valorProcurado = 410;

    int posicao = buscaBinariaIterativa(codigos, tamanho, valorProcurado);

    if (posicao != -1) {
        cout << "Codigo encontrado na posicao " << posicao << endl;
    } else {
        cout << "Codigo nao encontrado." << endl;
    }

    return 0;
}

No código iterativo, a função retorna a posição onde o valor foi encontrado ou o valor -1 caso o valor não exista no vetor, conforme estabelecido no pseudocódigo. O retorno de -1 é uma convenção comum para indicar ausência de resultado válido, apesar de não ser uma regra rígida e imutável.

A expressão usada para calcular o meio do conjunto foi:

int meio = inicio + (fim - inicio) / 2;

Esse método de cálculo é preferível à versão abaixo:

int meio = (inicio + fim) / 2;

porque em vetores muito grandes, calcular (inicio + fim) pode ultrapassar o limite de armazenamento de um inteiro. Como a forma inicio + (fim - inicio) / 2 evita esse risco, optamos por ela. Contudo, é válido ressaltar que em vetores pequenos, as duas formas costumam produzir o mesmo resultado.

Busca binária recursiva

Evoluindo nosso algoritmo, agora vamos aparesentar a versão recursiva. Ela expressa a busca binária como um problema que se chama novamente sobre uma parte menor do vetor. A cada chamada, o intervalo [inicio, fim] diminui. O caso-base ocorre quando o valor é encontrado ou quando inicio > fim.

O algoritmo de busca binária em C++ ficaria assim:

#include <iostream>

using namespace std;

int buscaBinariaRecursiva(int dados[], int inicio, int fim, int valorProcurado) {
    if (inicio > fim) {
        return -1;
    }

    int meio = inicio + (fim - inicio) / 2;

    if (dados[meio] == valorProcurado) {
        return meio;
    }

    if (valorProcurado < dados[meio]) {
        return buscaBinariaRecursiva(dados, inicio, meio - 1, valorProcurado);
    }

    return buscaBinariaRecursiva(dados, meio + 1, fim, valorProcurado);
}

int main() {
    int codigos[] = {101, 203, 305, 410, 512, 608, 777};
    int tamanho = 7;
    int valorProcurado = 608;

    int posicao = buscaBinariaRecursiva(codigos, 0, tamanho - 1, valorProcurado);

    if (posicao != -1) {
        cout << "Codigo encontrado na posicao " << posicao << endl;
    } else {
        cout << "Codigo nao encontrado." << endl;
    }

    return 0;
}

A versão recursiva é útil para mostrar uma característica da busca binária chamada “dividir para conquistar”, ou seja, a cada comparação, o algoritmo divide o intervalo de busca para aproximadamente metade do tamanho original.

Comparação entre versão iterativa e recursiva

A versão iterativa e a versão recursiva resolvem o mesmo problema e possuem a mesma complexidade assintótica de tempo: O(log n). A diferença está principalmente na forma de controle.

A versão iterativa controla o processo por meio de um laço. Em geral, é mais econômica em memória, pois não cria novas chamadas de função a cada passo. Cormen et al. (2012) observam, ao comparar versões recursivas e iterativas em buscas sobre árvores, que uma versão iterativa pode ser mais eficiente em muitos computadores por eliminar a sobrecarga da recursão. Embora o exemplo discutido pelos autores esteja relacionado a árvores de busca binária, o princípio também ajuda a compreender a diferença prática entre a busca binária iterativa e a recursiva em vetores.

A versão recursiva, por outro lado, é conceitualmente elegante. Ela evidencia que o problema original é reduzido a um subproblema da mesma natureza: buscar o mesmo valor em uma metade menor do vetor.

Para fins didáticos, podemos elencar os prós e contras de ambas as implementações na tabela a seguir:

CritérioIterativaRecursiva
LegibilidadeBoa, especialmente para quem já conhece o algoritmoExcelente, pois espelha diretamente a definição por indução do problema
Espaço extraΘ(1)Θ(log n) (pilha de chamadas)
Risco de stack overflowInexistentePresente em cenários extremos
Facilidade de depuraçãoMais direta (estado visível em variáveis de laço)Requer acompanhar múltiplos quadros de pilha
Uso didáticoReforça o conceito de invariante de laçoReforça o conceito de indução e casos base/recursivo

Do ponto de vista de engenharia de software, a versão iterativa é geralmente preferida em código de produção por sua eficiência de espaço e ausência de risco de estouro de pilha. A versão recursiva, por sua vez, tem grande valor pedagógico por evidenciar a estrutura de divisão e conquista de forma mais explícita, justificando sua presença constante em disciplinas introdutórias de algoritmos.

Análise de complexidade

A busca binária tem complexidade de tempo Θ(log n). Isso ocorre porque, a cada comparação, o tamanho do problema é dividido aproximadamente por dois.

Se o vetor possui n elementos, depois da primeira comparação restam aproximadamente (n / 2) elementos. Depois da segunda, (n / 4). Depois da terceira, (n / 8). O processo continua até que reste apenas um elemento ou nenhum elemento.

Formalmente, considere T(n) o tempo de execução da busca binária sobre um vetor de n elementos. A cada chamada, o algoritmo realiza uma quantidade constante de trabalho (uma comparação, o cálculo do centro) e, no pior caso, invoca-se recursivamente sobre um subvetor de aproximadamente (n / 2) elementos. Essa relação é expressa pela recorrência:

T(n)=T(n/2)+c,comT(1)=cT(n) = T(n/2) + c, \quad com \quad T(1) = c

Cormen et al. (2012) demonstram que recorrências desse formato — em que o problema é dividido por uma constante a cada chamada, com trabalho adicional constante — resultam em complexidade Θ(log n). Intuitivamente, a pergunta é: quantas vezes é possível dividir n por 2 até restar apenas 1 elemento? A resposta é log₂n, o que fundamenta o resultado.

Complexidade de tempo

CasoComplexidadeJustificativa
Melhor casoΘ(1)O elemento buscado está exatamente na posição central na primeira comparação.
Caso médioΘ(log n)Em média, o algoritmo converge após um número logarítmico de divisões.
Pior casoΘ(log n)O elemento está em uma extremidade ou não existe; o intervalo é reduzido até restar um único elemento.

Só para que você tenha uma ideia mais clara do que isso significa e possa dimensionar esse ganho, pense o seguinte: suponha um vetor com 1 milhão de elementos. A busca sequencial pode exigir, no pior caso, 1.000.000 de comparações, enquanto a busca binária necessita de, no máximo, cerca de 20 comparações — log₂(1.000.000) ≈ 20 (Ziviani, 2010). Esse é o ganho da busca binária em relação à sequencial para vetores grandes.

Complexidade de espaço

Aqui reside uma diferença prática relevante entre as duas versões implementadas:

  • Versão iterativa: complexidade de espaço Θ(1), pois utiliza apenas variáveis auxiliares (esquerda, direita, centro), independentemente do tamanho do vetor.
  • Versão recursiva: complexidade de espaço Θ(log n), pois cada chamada recursiva consome um novo quadro (stack frame) na pilha de execução, e a profundidade máxima da recursão é proporcional a log n.

Essa diferença é especialmente relevante em ambientes com pilha de execução limitada, ou ao lidar com vetores extremamente grandes, situação em que a recursão profunda pode levar a estouro de pilha (stack overflow), que é um risco inexistente na versão iterativa.

Cuidado com valores repetidos

Em muitos materiais introdutórios, a busca binária é apresentada sobre vetores ordenados e sem repetição. Martins (2009), por exemplo, descreve a busca binária nesse contexto didático, considerando vetor ordenado e sem dados repetidos.

Entretanto, em sistemas reais, pode haver valores repetidos. Nesse caso, a busca binária tradicional retorna uma das ocorrências, mas não necessariamente a primeira ou a última. Se for necessário encontrar a primeira ocorrência de um valor repetido, o algoritmo precisa ser adaptado.

Observe a versão a seguir. 

#include <iostream>

using namespace std;

int buscarPrimeiraOcorrencia(int dados[], int tamanho, int valorProcurado) {
    int inicio = 0;
    int fim = tamanho - 1;
    int resultado = -1;

    while (inicio <= fim) {
        int meio = inicio + (fim - inicio) / 2;

        if (dados[meio] == valorProcurado) {
            resultado = meio;
            fim = meio - 1;
        } else if (valorProcurado < dados[meio]) {
            fim = meio - 1;
        } else {
            inicio = meio + 1;
        }
    }

    return resultado;
}

int main() {
    int notas[] = {50, 60, 60, 60, 70, 80, 90};
    int tamanho = 7;
    int valorProcurado = 60;

    int posicao = buscarPrimeiraOcorrencia(notas, tamanho, valorProcurado);

    if (posicao != -1) {
        cout << "Primeira ocorrencia encontrada na posicao " << posicao << endl;
    } else {
        cout << "Valor nao encontrado." << endl;
    }

    return 0;
}

Repare que mesmo encontrando uma ocorrência do elemento procurado, a função não retorna posição obtida. Ela atualiza a variável fim, reduzindo o espaço de busca para verificar se há alguma ocorrência anterior à encontrada.

Busca binária em um cenário simples de trabalho

Considere um pequeno sistema acadêmico que armazena códigos de matrícula já ordenados. O objetivo é verificar rapidamente se uma matrícula está registrada.

#include <iostream>

using namespace std;

int buscarMatricula(int matriculas[], int tamanho, int matriculaProcurada) {
    int inicio = 0;
    int fim = tamanho - 1;

    while (inicio <= fim) {
        int meio = inicio + (fim - inicio) / 2;

        if (matriculas[meio] == matriculaProcurada) {
            return meio;
        }

        if (matriculaProcurada < matriculas[meio]) {
            fim = meio - 1;
        } else {
            inicio = meio + 1;
        }
    }

    return -1;
}

int main() {
    int matriculas[] = {1001, 1005, 1010, 1020, 1033, 1048, 1050, 1062};
    int tamanho = 8;
    int matriculaProcurada;

    cout << "Digite a matricula que deseja localizar: ";
    cin >> matriculaProcurada;

    int posicao = buscarMatricula(matriculas, tamanho, matriculaProcurada);

    if (posicao != -1) {
        cout << "Matricula localizada no indice " << posicao << "." << endl;
    } else {
        cout << "Matricula nao localizada." << endl;
    }

    return 0;
}

Esse exemplo é simples, mas representa um padrão recorrente em sistemas reais. A necessidade de consultar rapidamente se um identificador existe em uma coleção ordenada é mais comum do que parece. Em estruturas mais avançadas, a mesma ideia aparece em índices, árvores de busca, tabelas ordenadas e bancos de dados.

Quando usar e quando não usar busca binária

A busca binária deve ser usada quando os dados estão ordenados e quando há muitas operações de busca sobre a mesma coleção. Se o vetor já está ordenado, a busca binária é muito eficiente.

Outros exemplos onde pode-se aplicar a estratégia são:

  • Indexação de bancos de dados e sistemas de arquivos, onde estruturas ordenadas permitem localizar registros rapidamente.
  • Controle de versão (o comando git bisect, por exemplo, aplica o mesmo princípio de divisão para localizar o commit que introduziu um defeito).
  • Bibliotecas padrão de linguagens de programação, como as funções de busca em coleções ordenadas disponíveis em diversas linguagens.
  • Problemas de otimização por “busca binária na resposta”, técnica avançada em que o algoritmo não busca um valor em um vetor, mas sim a menor ou maior resposta que satisfaz uma condição monótona — extensão conceitual frequente em competições de programação.

Agora, se o vetor não está ordenado, talvez seja necessário avaliar o custo de ordená-lo antes de aplicar a busca binária. Se a aplicação fará apenas uma única busca em um vetor pequeno e desordenado, uma busca sequencial pode ser suficiente. Portanto, é preciso avaliar o contexto com calma e ponderar as possibilidades.

Conclusão

A busca binária é uma técnica essencial para estudantes de algoritmos e estruturas de dados porque demonstra, de forma clara, como uma boa estratégia algorítmica pode reduzir o custo de execução de uma tarefa. Enquanto a busca sequencial pode exigir até n comparações, a busca binária exige aproximadamente log2(n) comparações no pior caso, desde que o vetor esteja ordenado.

Dominar a busca binária ajuda o programador a compreender conceitos fundamentais como pré-condição, divisão do problema, atualização de limites, análise de complexidade, recursividade e eficiência computacional. Na prática profissional, essa compreensão prepara o estudante para estruturas mais sofisticadas, como árvores de busca binária, índices ordenados e algoritmos de consulta em grandes volumes de dados. Portanto, a busca binária é pequena em implementação, mas grande em importância conceitual.

Obrigado pela leitura e bons estudos!

Referências

CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: Elsevier, 2012.

MARTINS, Paulo Roberto. Algoritmos e estrutura de dados: análise e desenvolvimento de sistemas. São Paulo: Pearson Prentice Hall, 2009.

ZIVIANI, Nivio. Projeto de algoritmos: com implementações em Java e C++. 3 ed. São Paulo: Cengage Learning, 2010.

Tag

Artigos relacionados

Prof. Felipe Túlio de Castro - Blog | © Todos os direitos reservados, 2026