Busca sequencial e binária

Procurar um valor é uma das operações mais frequentes em um programa: um aluno pela matrícula, uma palavra no dicionário, um produto pelo código. Na análise de algoritmos, a busca sequencial e a busca binária serviram de exemplo para contar operações e comparar taxas de crescimento. Nesta página, olhamos para elas como algoritmos: variações, versões recursivas, problemas que parecem diferentes mas são resolvidos com a mesma ideia e os erros que mais aparecem ao implementá-las.

Em todas as funções, a busca recebe um vetor V com n elementos e um valor x, e devolve a posição de x em V, ou se x não estiver lá.

Busca sequencial

A busca sequencial compara x com cada elemento, do primeiro ao último, e para quando encontra. Ela não exige nada do vetor: funciona com os valores em qualquer ordem. O custo é proporcional à posição de x, e, no pior caso (x no fim ou ausente), são comparações com x.

int buscaSequencial(const int *V, int n, int x) {
    for (int i = 0; i < n; i++)
        if (V[i] == x)
            return i;
    return -1;
}

Repare que cada iteração faz dois testes: i < n (ainda há elementos?) e V[i] == x (é este?). As duas variações a seguir reduzem esse trabalho.

Busca com sentinela

Se x estiver garantidamente no vetor, o teste i < n é desnecessário: o laço vai parar quando encontrar x. A ideia da sentinela é garantir isso colocando uma cópia de x logo depois do último elemento, em V[n]. O laço fica com um único teste por iteração. No fim, se a posição encontrada for n, foi a sentinela que parou o laço, e x não estava no vetor.

/* V precisa ter espaço para n + 1 elementos */
int buscaSentinela(int *V, int n, int x) {
    V[n] = x;                       /* a sentinela garante que o laço para */
    int i = 0;
    while (V[i] != x)
        i++;
    return i < n ? i : -1;
}

O preço é que o vetor precisa ter uma posição a mais, e a função escreve nele (por isso o parâmetro não é mais const).

Busca em vetor ordenado

Se o vetor estiver em ordem crescente, a busca pode parar assim que encontrar um elemento maior que x: daquele ponto em diante, todos são maiores, e x não pode estar lá. Para valores ausentes que cairiam no meio do vetor, a busca termina mais cedo. O pior caso, porém, continua sendo comparações.

int buscaOrdenada(const int *V, int n, int x) {
    int i = 0;
    while (i < n && V[i] < x)
        i++;
    if (i < n && V[i] == x)
        return i;
    return -1;
}

O programa abaixo conta todas as comparações (com x e com o limite n) das três versões, em um vetor com 1000 valores pares de 0 a 1998:

A sentinela faz cerca de metade das comparações da versão básica. A busca ordenada só ganha quando x está ausente e cairia antes do fim (o 7): ela para no 8. Nos outros casos, faz o mesmo que a básica.

int buscaSequencialRec(const int *V, int n, int x) {
    if (n == 0)
        return -1;                      /* vetor vazio */
    if (V[n - 1] == x)
        return n - 1;
    return buscaSequencialRec(V, n - 1, x);
}

Busca binária

Em um vetor ordenado, dá para fazer muito melhor. A busca binária compara x com o elemento do meio do trecho em que ele pode estar. Se for igual, terminou. Se o elemento do meio for menor que x, toda a metade esquerda também é, e a busca continua só na metade direita. Se for maior, continua só na esquerda. A cada passo, metade dos candidatos é descartada.

A busca mantém dois índices, ini e fim, que delimitam o trecho V[ini..fim] em que x ainda pode estar:

1. 1

   Comece com o vetor inteiro#

   ini = 0 e fim = n - 1.

2. 2

   Enquanto o trecho não estiver vazio (ini <= fim)#

   Calcule o meio, m = ini + (fim - ini) / 2, e compare V[m] com x.

3. 3

   Decida#

   Se V[m] == x, devolva m. Se V[m] < x, o trecho passa a ser V[m+1..fim] (ini = m + 1). Se V[m] > x, passa a ser V[ini..m-1] (fim = m - 1).

4. 4

   Trecho vazio#

   Se ini > fim, não sobrou nenhum candidato: devolva .

O que garante que o algoritmo está certo é uma propriedade que vale no início de toda iteração, o invariante: se x está no vetor, então ele está em V[ini..fim]. No começo, o trecho é o vetor inteiro. A cada passo, só descartamos posições que não podem conter x. E o elemento do meio já foi comparado, então ele também sai (daí o + 1 e o - 1). Quando o trecho fica vazio, o invariante diz que x não está no vetor.

Como o trecho cai pela metade a cada iteração, a busca faz no máximo iterações: cerca de 20 para um milhão de elementos (veja a comparação com a sequencial).

Versão recursiva

A descrição da busca binária já é recursiva: procurar em um trecho é comparar com o meio e procurar em uma das metades. Os casos base são o trecho vazio (não encontrou) e o meio igual a x (encontrou). A função recebe os limites do trecho como parâmetros:

A versão recursiva imprime cada chamada, com recuo proporcional à profundidade. Procurando o 7, que não está no vetor, a última chamada recebe o trecho V[2..1], vazio, e devolve , que volta por todas as chamadas. Como o trecho cai pela metade a cada chamada, a profundidade da recursão é no máximo : cerca de 21 para um milhão de elementos, sem risco para a pilha.

Primeira e última ocorrência

Se o vetor tem valores repetidos, a busca binária encontra alguma ocorrência de x, não necessariamente a primeira. Em {1, 3, 3, 3, 3, 3, 3, 3, 5, 7, 7, 9}, procurando o 3, ela encontra o da posição 5. Para encontrar a primeira ocorrência, a ideia é não parar ao encontrar x: guardamos a posição como candidata e continuamos procurando na metade esquerda, onde pode haver outra ocorrência mais à esquerda.

A última ocorrência é simétrica (continua à direita). Com as duas, contar quantas vezes x aparece custa , mesmo que ele apareça milhares de vezes:

Uma variação próxima responde "em que posição x deveria entrar para o vetor continuar ordenado?", ou seja, qual é o primeiro elemento maior ou igual a x. É o que a tabela de símbolos com vetor ordenado usa para inserir uma chave nova, e é o segundo exercício de implementação desta página.

Busca binária na resposta

A busca binária não precisa de um vetor. O que ela precisa é de uma pergunta de sim ou não que seja monotônica: a resposta é "não" até um ponto e "sim" daí em diante (ou o contrário). Nesse caso, dá para encontrar o ponto de virada com perguntas, procurando sobre o intervalo de respostas possíveis.

Por exemplo, a raiz quadrada inteira de é o maior com . A pergunta "?" é "sim" para e "não" daí em diante. Então, buscamos em : quando m serve, ele é candidato e tentamos um maior. Quando não serve, tentamos um menor.

Dois cuidados com números grandes: o meio é calculado como ini + (fim - ini) / 2, e o teste é feito como m <= x / m, porque m * m estouraria o long long para m perto de . Para o maior long long, a busca faz só 63 iterações.

A mesma técnica resolve muitos problemas de "qual é o menor valor que serve?", como o último exercício desta página.

Sequencial ou binária?

Se o vetor não está ordenado, ordená-lo custa . Para uma única busca, não compensa: a sequencial resolve em . Para buscas, a sequencial custa , e ordenar e fazer buscas binárias custa , o que compensa já para maior que algumas dezenas. Se o vetor muda muito (inserções e remoções), manter a ordem fica caro, e o problema passa a pedir outra estrutura, como as árvores de busca.

Exercícios

Encontre e corrija o erro

Programa 1

O programa abaixo usa a busca binária na resposta para encontrar o maior em com menor ou igual a um limite. A função lastTrue devolve o último valor para o qual check é verdadeiro.

int m = ini + (fim - ini + 1) / 2;

Programa 2

int *V = malloc((n + 1) * sizeof(int));

Programa 3

int ini = 0, fim = n - 1, resposta = -1;
while (ini <= fim) {
    int m = ini + (fim - ini) / 2;
    if (V[m] == x) {
        resposta = m;
        fim = m - 1;
    } else if (V[m] < x) {
        ini = m + 1;
    } else {
        fim = m - 1;
    }
}
return resposta;

Programa 4

Implemente

Busca autoorganizada. Em muitas aplicações, alguns valores são procurados muito mais que outros. Uma busca sequencial pode tirar proveito disso reorganizando o vetor a cada busca bem-sucedida, para que os valores mais procurados fiquem perto do início. Implemente as duas estratégias clássicas de auto.h: mover para a frente (o valor encontrado vai para a posição 0, e os que estavam antes dele andam uma posição) e transposição (o valor encontrado troca de lugar com o anterior). As duas devolvem a posição em que o valor estava.

lowerBound. A biblioteca padrão de C++ tem a função std::lower_bound, que, em um trecho ordenado, devolve o primeiro elemento maior ou igual a x. Implemente a versão em C de lowerbound.h, que recebe o trecho como dois ponteiros, ini (o primeiro elemento) e fim (uma posição depois do último), e devolve um ponteiro para o elemento encontrado, ou fim se nenhum elemento for maior ou igual a x. Por exemplo, em {1, 3, 3, 3, 5, 7, 7, 9, 12}, lowerBound devolve a posição 1 para x = 3, a posição 4 para x = 4 e fim para x = 13. Os testes fazem 300 mil buscas em vetores com um milhão de elementos, com muitos repetidos.

Menor capacidade do caminhão. Uma fila de pacotes precisa ser entregue, nesta ordem, por um caminhão que faz uma viagem por dia, levando os próximos pacotes da fila enquanto a soma dos pesos não passar da sua capacidade. Implemente menorCapacidade, que devolve a menor capacidade que permite entregar tudo em no máximo dias viagens. Por exemplo, com os pesos 1, 2, ..., 10 e 5 dias, a resposta é 15 (as viagens levam 1 a 5, 6 e 7, 8, 9 e 10). Os testes têm 200 mil pacotes com pesos de até um bilhão.

Referências

• T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein. Algoritmos: Teoria e Prática. 3ª ed. Elsevier, 2012.
• N. Ziviani. Projeto de Algoritmos com Implementações em Pascal e C. 3ª ed. Cengage Learning, 2010. Capítulo 5 (pesquisa em memória primária).
• D. E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching. 2ª ed. Addison-Wesley, 1998. Seção 6.1 (busca sequencial, sentinela e busca autoorganizada) e 6.2.1 (busca binária).
• J. Bloch. Extra, Extra: Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Google Research Blog, 2006.