Busca binária

1. Introdução à Busca Binária

A busca binária é um algoritmo clássico de pesquisa em vetores que reduz drasticamente o tempo de busca ao explorar a propriedade de ordenação dos dados. Enquanto a busca linear percorre elemento por elemento — com complexidade O(n) —, a busca binária opera em O(log n), o que significa que para um vetor de 1 milhão de elementos, a busca linear pode exigir até 1 milhão de comparações, enquanto a binária realiza no máximo 20.

O pré-requisito fundamental para aplicar a busca binária é que o vetor esteja ordenado. Sem essa condição, o algoritmo falha completamente, pois sua lógica depende da capacidade de descartar metade do espaço de busca com base na comparação com o elemento central.

2. Funcionamento do Algoritmo

O princípio é simples e elegante: dividir para conquistar. A cada iteração, o algoritmo compara o elemento alvo com o elemento central do intervalo atual:

  1. Se o elemento central é igual ao alvo, a busca termina com sucesso.
  2. Se o alvo é menor que o central, descarta-se a metade direita (elementos maiores).
  3. Se o alvo é maior que o central, descarta-se a metade esquerda (elementos menores).

Esse processo se repete até encontrar o elemento ou até o intervalo se tornar vazio.

Exemplo prático: Buscar o valor 23 no vetor ordenado [2, 5, 8, 12, 16, 23, 38, 45, 56, 72].

  • Passo 1: meio = índice 4 (valor 16). 23 > 16 → descarta metade esquerda.
  • Passo 2: novo intervalo [23, 38, 45, 56, 72], meio = índice 7 (valor 45). 23 < 45 → descarta metade direita.
  • Passo 3: novo intervalo [23, 38], meio = índice 5 (valor 23). 23 == 23 → encontrado!

3. Implementação Iterativa em C

A versão iterativa utiliza um loop while para controlar os índices inicio e fim, que delimitam o espaço de busca. O cálculo seguro do meio evita overflow de inteiros.

#include <stdio.h>

int busca_binaria_iterativa(int vetor[], int tamanho, int alvo) {
    int inicio = 0;
    int fim = tamanho - 1;

    while (inicio <= fim) {
        // Cálculo seguro: evita overflow em vetores muito grandes
        int meio = inicio + (fim - inicio) / 2;

        if (vetor[meio] == alvo) {
            return meio;  // Elemento encontrado
        } else if (vetor[meio] < alvo) {
            inicio = meio + 1;  // Busca na metade direita
        } else {
            fim = meio - 1;  // Busca na metade esquerda
        }
    }

    return -1;  // Elemento não encontrado
}

int main() {
    int dados[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72};
    int tamanho = sizeof(dados) / sizeof(dados[0]);
    int alvo = 23;

    int resultado = busca_binaria_iterativa(dados, tamanho, alvo);
    if (resultado != -1) {
        printf("Elemento %d encontrado no índice %d\n", alvo, resultado);
    } else {
        printf("Elemento %d não encontrado\n", alvo);
    }

    return 0;
}

A função recebe três parâmetros: o vetor, seu tamanho e o valor alvo. Retorna o índice do elemento ou -1 caso não exista.

4. Implementação Recursiva em C

A versão recursiva é mais declarativa e reflete diretamente a natureza do algoritmo. O caso base ocorre quando o intervalo é inválido (inicio > fim).

#include <stdio.h>

int busca_binaria_recursiva(int vetor[], int inicio, int fim, int alvo) {
    if (inicio > fim) {
        return -1;  // Caso base: elemento não encontrado
    }

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

    if (vetor[meio] == alvo) {
        return meio;
    } else if (vetor[meio] < alvo) {
        return busca_binaria_recursiva(vetor, meio + 1, fim, alvo);
    } else {
        return busca_binaria_recursiva(vetor, inicio, meio - 1, alvo);
    }
}

int main() {
    int dados[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72};
    int tamanho = sizeof(dados) / sizeof(dados[0]);
    int alvo = 23;

    int resultado = busca_binaria_recursiva(dados, 0, tamanho - 1, alvo);
    if (resultado != -1) {
        printf("Elemento %d encontrado no índice %d\n", alvo, resultado);
    } else {
        printf("Elemento %d não encontrado\n", alvo);
    }

    return 0;
}

Note que a versão recursiva exige que inicio e fim sejam passados como argumentos, permitindo que cada chamada trabalhe com um subintervalo diferente.

5. Casos Especiais e Tratamento de Erros

Elemento não encontrado: Ambas as implementações retornam -1, que é um índice inválido em C (vetores começam em 0). Essa convenção é universal.

Vetor vazio: Se tamanho == 0, a versão iterativa não entra no loop e retorna -1 imediatamente. A versão recursiva recebe inicio=0, fim=-1, e a condição inicio > fim é verdadeira, retornando -1.

Overflow no cálculo do meio: A expressão (inicio + fim) / 2 pode causar overflow se inicio + fim exceder INT_MAX. A forma segura inicio + (fim - inicio) / 2 evita esse problema e deve ser sempre preferida.

6. Variações da Busca Binária

A busca binária clássica encontra um elemento igual ao alvo, mas variações resolvem problemas mais específicos:

Busca pelo primeiro elemento igual ao alvo (lower_bound):

int primeiro_igual(int vetor[], int tamanho, int alvo) {
    int inicio = 0, fim = tamanho;
    while (inicio < fim) {
        int meio = inicio + (fim - inicio) / 2;
        if (vetor[meio] < alvo) {
            inicio = meio + 1;
        } else {
            fim = meio;
        }
    }
    return (inicio < tamanho && vetor[inicio] == alvo) ? inicio : -1;
}

Busca pelo último elemento igual ao alvo (upper_bound - 1):

int ultimo_igual(int vetor[], int tamanho, int alvo) {
    int inicio = 0, fim = tamanho;
    while (inicio < fim) {
        int meio = inicio + (fim - inicio) / 2;
        if (vetor[meio] <= alvo) {
            inicio = meio + 1;
        } else {
            fim = meio;
        }
    }
    return (inicio > 0 && vetor[inicio - 1] == alvo) ? inicio - 1 : -1;
}

Essas variações são essenciais para trabalhar com vetores que contêm elementos duplicados.

7. Aplicações Práticas e Exemplos

Busca em vetores de structs:

#include <stdio.h>
#include <string.h>

typedef struct {
    int id;
    char nome[50];
} Aluno;

int busca_aluno_por_id(Aluno alunos[], int tamanho, int id_alvo) {
    int inicio = 0, fim = tamanho - 1;
    while (inicio <= fim) {
        int meio = inicio + (fim - inicio) / 2;
        if (alunos[meio].id == id_alvo) {
            return meio;
        } else if (alunos[meio].id < id_alvo) {
            inicio = meio + 1;
        } else {
            fim = meio - 1;
        }
    }
    return -1;
}

Busca em arrays de strings: A mesma lógica se aplica, usando strcmp() para comparação.

Uso com algoritmos de ordenação: A busca binária é frequentemente combinada com qsort() da biblioteca padrão C. Primeiro ordena-se o vetor com qsort, depois aplica-se a busca binária.

8. Limitações e Considerações Finais

A principal limitação da busca binária é a dependência de dados ordenados. Ordenar um vetor grande pode ser caro (O(n log n) para algoritmos eficientes), e se as inserções forem frequentes, manter a ordenação pode ser inviável.

Para dados não ordenados, alternativas como tabelas hash (O(1) médio) ou árvores binárias de busca (O(log n) médio) são mais adequadas, embora exijam mais memória e complexidade de implementação.

Resumo das vantagens e desvantagens:

Vantagens Desvantagens
O(log n) extremamente rápido Requer vetor ordenado
Baixo uso de memória (algoritmo in-place) Inserções/remoções frequentes exigem reordenação
Implementação simples e previsível Não funciona com listas encadeadas (sem acesso aleatório)
Comportamento determinístico Pior caso ainda é O(log n), mas busca linear pode ser mais rápida em vetores muito pequenos

A busca binária é um dos algoritmos mais elegantes e fundamentais da Ciência da Computação. Dominá-la em C — tanto na forma iterativa quanto recursiva — é essencial para qualquer programador que trabalhe com estruturas de dados ordenadas.

Referências