Binary search is to algorithms
what a wheel is to mechanics:
It is simple, elegant, and immensely important.
— Udi Manber,
Introduction to Algorithms
Binary search is a notoriously tricky algorithm
to program correctly.
It took seventeen years after its invention
until the first correct version of binary search
was published!
— Steven Skiena, The Algorithm Design Manual
Este capítulo estuda o seguinte problema de busca: encontrar um dado número em um vetor ordenado de números. Mais especificamente, dado um inteiro x e um vetor crescente v[0..n-1] de inteiros,
encontrar um índice m tal que v[m] == x .
É claro que nem toda instância desse problema tem solução. Considere, por exemplo, as instâncias em que n vale 0 e aquelas em que v[3] < x < v[4].
Sumário:
Comecemos por adotar uma formulação mais geral e mais interessante do problema: encontrar o lugar no vetor onde x deveria estar. Mais exatamente, dado x e um vetor crescente v[0..n-1], queremos encontrar um índice j tal que
v[j-1] < x ≤ v[j] .
Para obter uma solução do problema original, basta comparar x com v[j].
Para tirar o máximo proveito dessa formulação do problema, devemos permitir que a solução j assuma os valores 0 e n. Nesses dois casos, a expressão v[j-1] < x ≤ v[j] deve ser interpretada com bom senso: se j == 0, a expressão se reduz a x ≤ v[0] , pois v[-1] não está definido; se j == n, a expressão se reduz a v[n-1] < x , pois v[n] não está definido. Tudo se passa como se nosso vetor tivesse um componente imaginário v[-1] com valor −∞ e um componente imaginário v[n] com valor +∞.
No exemplo a seguir, se x vale 555, a solução j do problema é 4; se x vale 800, a solução é 8; e se x vale 1000, a solução é 13.
| 0 | n-1 | |||||||||||
| 111 | 222 | 333 | 444 | 555 | 555 | 666 | 777 | 888 | 888 | 888 | 999 | 999 |
Vamos examinar dois algoritmos para o problema: um óbvio mas lento e outro sofisticado e muito mais rápido.
int verifica (int v[], int n) {
int anterior = v[0], sim = 1;
for (int i = 1; i < n && sim; ++i) {
if (anterior > v[i]) sim = 0;
anterior = v[i]; }
return sim; }
Comecemos com um algoritmo óbvio, que examina um a um todos os elementos do vetor. Eis uma implementação do algoritmo:
// Esta função recebe um inteiro x e um vetor
// crescente v[0..n-1] e devolve um índice j
// em 0..n tal que v[j-1] < x <= v[j].
int
buscaSequencial (int x, int n, int v[]) {
int j = 0;
while (j < n && v[j] < x)
++j;
return j;
}
Quantas iterações a função faz? Ou melhor, quantas comparações faz entre x e elementos de v? No pior caso, x é comparado com cada elemento do vetor e portanto o número total de comparações é n . Assim, por exemplo, se o tamanho do vetor for multiplicado por 100, o número de comparações também será multiplicado por 100.
O consumo de tempo da função é proporcional ao número de comparações que envolvem x, e portanto proporcional a n no pior caso.
É possível resolver o problema em menos tempo? É possível resolver o problema sem comparar x com cada um dos elementos do vetor? A resposta é afirmativa, como veremos a seguir.
int buscaSeq2 (int x, int n, int v[]) {
int j;
for (j = 0; j < n; ++j)
if (x <= v[j]) break;
return j; }
int buscaSeq3 (int x, int n, int v[]) {
int j = 0;
while (v[j] < x && j < n) ++j;
return j; }
int buscaSeq4 (int x, int n, int v[]) {
if (n == 0) return 0;
if (x > v[n-1]) return n;
return buscaSeq4 (x, n-1, v); }
Existe um algoritmo muito mais rápido que a busca sequencial. Ele é análogo ao método que se usa para encontrar um nome em uma lista telefônica antiga, aquela que parece um livro. É claro que a ideia só funciona porque o vetor está ordenado.
// Esta função recebe um inteiro x // e um vetor crescente v[0..n-1] // e devolve um índice j em 0..n // tal que v[j-1] < x <= v[j]. int buscaBinaria (int x, int n, int v[]) { int e = -1, d = n; // atenção! while (e < d-1) { int m = (e + d)/2; if (v[m] < x) e = m; else d = m; } return d; }
Simples e limpo!
Os nomes das variáveis não foram escolhidos ao acaso:
e lembra esquerda
,
m lembra meio
e
d lembra direita
.
O resultado da divisão por 2 na expressão
(e+d)/2 é automaticamente
truncado,
pois as variáveis são do tipo int.
Por exemplo,
se e vale 6 e d vale 9,
a expressão
(e+d)/2 vale 7.
| 0 | e | d | n-1 | |||||||||
| 111 | 222 | 333 | 444 | 555 | 555 | 666 | 777 | 888 | 888 | 888 | 999 | 999 |
A ideia da busca binária (= binary search) é um verdadeiro ovo de Colombo. Essa ideia é o ponto de partida de algoritmos eficientes para muitos problemas.
e = -1; d = nda função buscaBinaria pelas três linhas a seguir. Discuta essa variante do código.
if (v[n-1] < x) return n;
if (x <= v[0]) return 0;
// agora v[0] < x <= v[n-1]
e = 0; d = n-1;
while (e < d-1)for trocado por
while (e < d)? ou por
while (e <= d-1)? Que acontece se trocarmos
(e + d)/2por
(e + d - 1)/2ou por
(e + d + 1)/2ou por
(d - e)/2? Que acontece se
if (v[m] < x)for trocado por
if (v[m] <= x)? Que acontece se
e = mfor trocado por
e = m+1ou por
e = m-1? Que acontece se
d = mfor trocado por
d = m+1ou por
d = m-1?
Para entender a função buscaBinaria, basta verificar que no início de cada repetição do while, imediatamente antes da comparação de e com d-1, vale a relação
v[e] < x ≤ v[d] .
Essa relação é, portanto, invariante. (O algoritmo foi construído a partir desse invariante!) Note a semelhança entre o invariante e o objetivo v[j-1] < x ≤ v[j] que estamos perseguindo. O invariante vale, em particular, no início da primeira iteração: basta imaginar que v[-1] vale −∞ e v[n] vale +∞.
No início de cada iteração, em virtude do invariante, temos v[e] < v[d] e portanto e < d, uma vez que o vetor é crescente. No início da última iteração, temos e >= d-1 e portanto e == d-1. A relação invariante garante agora que, ao devolver d, a função está se comportando como prometeu!
Em cada iteração temos e < m < d (por quê?). Logo, tanto d - m quanto m - e são estritamente menores que d - e. Portanto, a sequência de valores da expressão d - e é estritamente decrescente. É por isso que a execução do algoritmo termina, mais cedo ou mais tarde.
Quantas iterações a função buscaBinaria executa ao processar um vetor com n elementos? No início da primeira iteração, d - e vale aproximadamente n. No início da segunda, vale aproximadamente n/2. No início da terceira, aproximadamente n/4. No início da k+1-ésima, aproximadamente n/2k. Quando k passar de log n , o valor da expressão n/2k fica menor que 1 e a execução do algoritmo para. (Veja o exercício de cálculo de log n em outra página.) Logo, o número de iterações é aproximadamente
log n
tanto no pior caso quanto no melhor. O número aproximado de comparações de x com elementos do vetor também é log n. Veja alguns exemplos quando n é potência de 2:
| n | 32 | 1024 | 32768 | 1048576 | 33554432 | … | |
| log n | 5 | 10 | 15 | 20 | 25 | … |
O valor de log n cresce muito devagar pois log transforma multiplicações em adições. Por exemplo, se a busca em um vetor de tamanho n exige C comparações, então a busca em um vetor de tamanho 2n exigirá apenas C+1 comparações, a busca em um vetor de tamanho 8n exigirá apenas C+3 comparações, e a busca em um vetor de tamanho 100n exigirá menos que C+7 comparações.
O consumo de tempo da função buscaBinaria é proporcional ao número de comparações de x com elementos de v. O consumo de tempo é, portanto, proporcional a log n.
Implementações de busca binária
exigem cuidado e atenção aos detalhes.
É muito fácil escrever uma implementação que dá respostas erradas
ou entra em loop
.
Os exercícios abaixo discutem versões alternativas da
função buscaBinaria,
diferentes da que examinamos acima.
Todas procuram encontrar x em
v[0..n-1].
Todas produzem (ou deveriam produzir)
um índice j em 0..n
tal que v[j-1] < x ≤ v[j].
e = 0; d = n;
while (e < d) { // v[e-1] < x <= v[d]
m = (e + d)/2;
if (v[m] < x) e = m+1;
else d = m;
} // e == d
return d;
e = 0; d = n-1;
while (e <= d) { // v[e-1] < x <= v[d+1]
m = (e + d)/2;
if (v[m] < x) e = m+1;
else d = m-1; } // e == d+1
return d+1;
e = -1; d = n-1;
while (e < d) {
m = (e + d)/2;
if (v[m] < x) e = m;
else d = m-1; }
return d+1;
e = -1; d = n-1;
while (e < d) {
m = (e + d + 1)/2;
if (v[m] < x) e = m;
else d = m-1; }
return d+1;
Para formular uma versão recursiva da busca binária
é preciso generalizar ligeiramente o problema,
trocando v[0..n-1] por v[a..b].
A ponte entre a formulação básica e a generalizada
é uma função-embalagem
(= wrapper-function)
buscaBinaria2
que apenas repassa o serviço
para uma função recursiva bb.
// Esta função recebe um vetor crescente
// v[0..n-1] e um inteiro x e devolve um
// índice j em 0..n tal que
// v[j-1] < x <= v[j].
int
buscaBinaria2 (int x, int n, int v[]) {
return bb (x, -1, n, v);
}
// Recebe um vetor crescente v[e+1..d-1] e
// um inteiro x tal que v[e] < x <= v[d] e
// devolve um índice j em e+1..d tal que
// v[j-1] < x <= v[j].
static int
bb (int x, int e, int d, int v[]) {
if (e == d-1) return d;
else {
int m = (e + d)/2;
if (v[m] < x)
return bb (x, m, d, v);
else
return bb (x, e, m, v);
}
}
(A palavra-chave static está aí apenas para indicar que a função bb tem caráter auxiliar, e não deve ser invocada diretamente pelo usuário do algoritmo de busca binária.)
Qual a profundidade da recursão na função bb? Ou seja, quantas vezes bb chama a si mesma? Resposta: cerca de log n vezes.
int buscaBinaria3 (int x, int n, int v[]) {
if (v[n-1] < x) return n;
if (x <= v[0]) return 0;
return bb (x, 0, n-1, v); }
int bb2 (int x, int e, int d, int v[]) {
if (e > d) return d+1;
else {
int m = (e + d)/2;
if (v[m] < x)
return bb2 (x, m+1, d, v);
else
return bb2 (x, e, m-1, v); } }
<e
≤se referem à ordem lexicográfica.