Busca Binária

Aléssio Miranda Júnior

Prática: Busca Binária

Estes slides constituem um roteiro prático para entender, comparar e experimentar a busca sequencial e a busca binária, com ênfase em:

metáforas intuitivas (dicionário, jogo de adivinhação);
pré-condições para usar a busca binária com segurança;
implementações em código (Java, JavaScript e pseudocódigo);
análise de complexidade e comparação com a busca linear;
exercícios práticos guiados para fixar o conteúdo.

Motivação: Como Procurar em uma Lista?

Suponha que você tenha uma lista de valores representando:

Notas de alunos em uma turma;
Códigos de produtos em um estoque;
IDs de usuários em um sistema.

Pergunta central:

Dado um valor x, ele está na lista?
Se sim, em qual posição?

Busca Sequencial (Linear)

Quando não sabemos nada sobre a ordem dos elementos (lista não ordenada):

A opção mais simples é percorrer um a um;
Começamos na posição 0 (ou 1) e vamos até o fim;
A qualquer momento:
- Se encontramos x, paramos e retornamos a posição;
- Se acabar a lista, concluímos que não está presente.

Visualizando a Busca Sequencial

Cada quadrado representa uma posição do vetor;
A seta percorre os elementos em ordem;
Em média, percorremos metade da lista para encontrar o elemento;
No pior caso, percorremos todo o vetor.

Código: Busca Sequencial em JavaScript

function buscaSequencial(umVetor, item) {
    let pos = 0;
    let achou = false;

    while (pos < umVetor.length && !achou) {
        if (umVetor[pos] === item) {
            achou = true;
        } else {
            pos = pos + 1;
        }
    }

    return achou;
}

Complexidade da Busca Sequencial

Melhor caso: o elemento está logo na primeira posição
- 1 comparação ⇒ ((1)).
Pior caso: o elemento está na última posição ou não está na lista
- são feitas N comparações.
Caso médio: elemento encontrado após () comparações.

Portanto, a busca sequencial é um algoritmo (O(n)).

Aproveitando a Ordem: Motivação para a Busca Binária

E se a lista já estiver ordenada?

Exemplo: dicionário de palavras em ordem alfabética;
Lista de números inteiros do menor para o maior;
Coleção de registros indexados por ID.

Nesses casos, podemos usar uma estratégia bem mais rápida:

A busca binária explora o fato de que a coleção está ordenada para eliminar metade dos elementos a cada passo.

Metáfora: Procurando em um Dicionário

Queremos encontrar a palavra “limão” em um dicionário:

Abrimos o dicionário no meio;
A palavra da página é, por exemplo, “mamão”;
Sabemos que “limão” vem antes de “mamão” no alfabeto;
Eliminamos toda a metade posterior das páginas;
Repetimos o processo na metade restante, sempre abrindo no meio.

A cada passo, metade das possibilidades é descartada.

Visualização da Busca Binária

Sempre olhamos para o meio do intervalo atual;
Comparamos o elemento do meio com o valor buscado;
Dependendo do resultado:
- Eliminamos a metade esquerda ou a metade direita;
- Ou encontramos o elemento.

Pré-Condição Crucial

Para usar a busca binária corretamente, é obrigatório:

O vetor ou lista estar ordenado (crescente ou decrescente, de forma conhecida);
A ordenação ser consistente com as comparações (<, >, ==);
Não alterar a coleção (inserção, remoção ou reordenação) durante a busca.

Se a lista não estiver ordenada, a busca binária:

Pode retornar resultados errados;
Pode entrar em loop infinito em algumas implementações defeituosas.

Pseudocódigo da Busca Binária

BUSCA-BINÁRIA (V[], início, fim, e)
    i recebe o índice do meio entre início e fim
    se (V[i] = e) então
        devolva o índice i   # elemento e encontrado
    fimse
    se (início = fim) então
        não encontrou o elemento procurado
    senão
        se (V[i] vem antes de e) então
            BUSCA-BINÁRIA(V, i+1, fim, e)
        senão
            BUSCA-BINÁRIA(V, início, i-1, e)
        fimse
    fimse

Implementação Iterativa em Java

public static int buscaBinaria(int[] array, int valor) {
    int inicio = 0;
    int fim = array.length - 1;

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

        if (array[meio] == valor) {
            return meio; // encontrou
        }

        if (valor > array[meio]) {
            inicio = meio + 1;   // procura na metade direita
        } else {
            fim = meio - 1;      // procura na metade esquerda
        }
    }
    return -1; // não encontrou
}

Implementação Recursiva em Java

public static int buscaBinariaRecursiva(int[] vetor,
                                        int valorBuscado,
                                        int inicio,
                                        int fim) {
    if (inicio > fim) {
        return -1; // intervalo vazio, não encontrou
    }

    int meio = (inicio + fim) / 2;

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

Implementação em JavaScript

function buscaBinaria(umVetor, item) {
    let prim = 0;
    let ult = umVetor.length - 1;
    let achou = false;

    while (prim <= ult && !achou) {
        let meioLista = Math.floor((prim + ult) / 2);

        if (umVetor[meioLista] === item) {
            achou = true;
        } else if (item < umVetor[meioLista]) {
            ult = meioLista - 1;
        } else {
            prim = meioLista + 1;
        }
    }
    return achou;
}

Análise de Complexidade: Intuição

Em cada iteração:

Olhamos para o meio do intervalo;
Eliminamos metade dos elementos restantes.

Portanto, o número de passos necessários é da ordem de:

Quantas vezes conseguimos dividir (n) por 2 até chegar em 1?
Resposta: (_2 n).

A busca binária é, portanto, um algoritmo de complexidade ((n)).

Comparando Busca Sequencial e Binária

Busca Sequencial
- Não requer ordenação;
- Complexidade: (O(n));
- Útil para listas pequenas ou raramente acessadas.
Busca Binária
- Requer vetor ordenado;
- Complexidade: (O(n));
- Excelente para listas grandes e com muitas operações de busca.

Exemplo Passo a Passo (1/2)

Considere o vetor ordenado:

V = [-2, 0, 4, 7, 8, 9, 11]

Objetivo: buscar o valor 7.

inicio = 0, fim = 6
meio = 3 ⇒ V[3] = 7
→ Achamos o elemento na primeira verificação.

Exemplo Passo a Passo (2/2)

Agora, buscar o valor 5 no mesmo vetor:

inicio = 0, fim = 6
meio = 3 ⇒ V[3] = 7
5 < 7 ⇒ novo intervalo: inicio = 0, fim = 2
meio = 1 ⇒ V[1] = 0
5 > 0 ⇒ novo intervalo: inicio = 2, fim = 2
meio = 2 ⇒ V[2] = 4
5 > 4 ⇒ novo intervalo: inicio = 3, fim = 2 (intervalo vazio)

Conclusão: 5 não está no vetor.

Exercício Teórico Rápido

Considere o seguinte problema:

Temos um vetor ordenado de n números distintos;
Recebemos m perguntas do tipo: “o número x está no vetor?”;
Para cada x, devemos imprimir:
- -1 se o número não estiver no vetor;
- Ou a posição em que ele se encontra (indexado de 1 a n).

Perguntas:

Qual a complexidade de resolver esse problema com busca linear?
Qual a complexidade usando busca binária para cada consulta?

Resposta: Complexidade do Exercício

Busca Linear
- Cada busca custa (O(n));
- Temos (m) buscas;
- Complexidade total: (O(n m)).
Busca Binária
- Ordenar o vetor (se já não vier ordenado):
  - custo (O(n n)) em geral (por exemplo, Arrays.sort em Java);
- Cada busca binária custa (O(n));
- Com (m) buscas, custo adicional (O(m n));
- Complexidade total: (O((n + m)n)).

Comparação Numérica

Suponha:

(n = 10^5) e (m = 10^5).
Busca Linear:
- (O(n m) = O(10^{10})) operações (impraticável em geral).
Busca Binária:
- (O((n + m)n) O(2 ^5 ));
- Cerca de (3,4 ^6) operações (viável).

Moral da história: para muitas buscas em vetores grandes, a busca binária é extremamente vantajosa.

Experimento Prático Sugerido (1/2)

Implemente em Java (ou outra linguagem que preferir):

Uma função de busca linear;
Uma função de busca binária;
Um método que:
- Gera um vetor ordenado de tamanho N;
- Gera m valores a serem buscados;
- Mede o tempo total gasto pelas duas abordagens.

Experimento Prático Sugerido (2/2)

Sugestão de código para comparação de tempos em Java:

int N = 100000;
int M = 100000;
int[] vetor = new int[N];

for (int i = 0; i < N; i++) {
    vetor[i] = i * 2;
}

int[] consultas = new int[M];
Random rand = new Random();
for (int i = 0; i < M; i++) {
    consultas[i] = rand.nextInt(2 * N);
}

long t1 = System.currentTimeMillis();
for (int x : consultas) {
    // chamada da busca linear
}
long tempoLinear = System.currentTimeMillis() - t1;

long t2 = System.currentTimeMillis();
for (int x : consultas) {
    // chamada da busca binária
}
long tempoBinaria = System.currentTimeMillis() - t2;

System.out.println("Linear: " + tempoLinear + " ms");
System.out.println("Binária: " + tempoBinaria + " ms");

Cuidados Comuns e Bugs Clássicos

Alguns problemas típicos em implementações de busca binária:

Erros no cálculo de meio (por exemplo, não atualizar corretamente inicio e fim);
Esquecer o caso de parada e gerar loop infinito;
Esquecer que o vetor deve estar ordenado;
Usar índices fora dos limites do vetor (acesso inválido).

Recomendação:

Testar com vetores pequenos e conhecidos;
Testar casos em que o elemento:
- Está no começo;
- Está no meio;
- Está no fim;
- Não está presente.

Exercício de Implementação Guiado

Implemente um programa que:

Lê dois inteiros n e m;
Lê um vetor ordenado de n inteiros distintos;
Lê m inteiros (consultas);
Para cada consulta:
- Usa busca binária para verificar se o número está no vetor;
- Imprime a posição (indexada de 1 a n) ou -1 caso não encontre.

Tente primeiro usando busca linear, depois substitua pela busca binária e compare o desempenho.

Para Pensar Além

A ideia de dividir o problema pela metade aparece em vários contextos:
- Encontrar o máximo em uma sequência que cresce e depois decresce;
- Otimizar decisões por busca binária na resposta (técnica de “binary search on answer”);
- Ajustar parâmetros em algoritmos (por exemplo, limite máximo de memória, tempo, etc.).

Pergunta final:

Em quais outros problemas você consegue imaginar que eliminar metade das possibilidades a cada passo seria uma boa estratégia?

Conclusões

A busca sequencial é simples, porém lenta para vetores grandes;
A busca binária é extremamente eficiente, desde que:
- O vetor esteja ordenado;
- A implementação respeite os limites de índice e os casos de parada;
Entender bem a busca binária é fundamental para:
- Resolver problemas clássicos de competição e entrevistas;
- Compreender melhor algoritmos de alto desempenho em estruturas de dados.

Na próxima prática, vamos usar esse conhecimento como base para outros algoritmos de busca e ordenação.