Algoritmos: busca binária (versão simplificada)
5/14/13 6:56 PM
Projeto de Algoritmos
Home
|
Prefácio
|
Livros
|
Sítios WWW
|
Índice
Esta é uma versão simplificada da página. Veja também a versão completa.
"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
Busca em vetor ordenado
Esta página estuda o seguinte problema básico: determinar se um dado número está ou não
está em um dado vetor ordenado. Mais precisamente, dado um número x e
um vetor crescente v[0..n-1], encontrar um índice m tal que v[m] == x .
É claro que o problema pode não ter solução. Este é o caso, por exemplo, se o vetor é vazio,
ou seja, se n vale 0.
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 e lento e outro sofisticado e
muito mais rápido.
Veja o verbete Binary search algorithm na Wikipedia.
Busca sequencial
Comecemos com um algoritmo simples e óbvio:
//
//
//
//
A função abaixo recebe um número x e um vetor
crescente v[0..n-1]. Ela devolve um índice m
em 0..n-1 tal que v[m] == x. Se tal m não existe,
a função devolve -1.
int
buscaSequencial( int x, int n, int v[]) {
int m = 0;
while (m < n && v[m] < x) ++m;
http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html
Page 1 of 8
Algoritmos: busca binária (versão simplificada)
5/14/13 6:56 PM
if (m < n && v[m] == x)
return m;
else
return -1;
}
O valor de m muda a cada iteração, mas a relação v[m-1] < x é invariante: ela vale no
início de cada iteração. Mais precisamente, essa relação invariante vale imediatamente
antes da comparação de m com n. Ela vale até mesmo no começo da primeira iteração se
estivermos dispostos a imaginar que v[-1] vale −∞.
A relação invariante vale, em particular, no início da última iteração, quando m ≥ n ou
v[m] ≥ x. Portanto, se a função devolve -1 então x é, de fato, diferente de todos os
elementos do vetor v[0..n-1].
Quantas comparações de x com elementos de v essa função faz? A resposta, mesmo no pior
caso, é
n
.
O consumo de tempo da função é proporcional ao número de comparações. Se 1
microssegundo decorre entre duas comparações consecutivas, então uma busca em n
elementos consome n microssegundos e uma busca em 8n elementos consome 8n
microssegundos.
É possível resolver o problema com menos comparações? Em outras palavras, é possível
resolver o problema sem comparar x com cada um dos elementos do vetor? A resposta é
afirmativa, como veremos adiante.
Exercícios
1. Critique a seguinte versão da função buscaSequencial:
int busca( int
int m = 0;
while (v[m]
if (v[m] ==
else return
}
x, int n, int v[]) {
< x && m < n) ++m;
x) return m;
-1;
2. Discuta a seguinte versão recursiva da função buscaSequencial:
int busca2( int x, int n, int v[]) {
if (n == 0) return -1;
if (x == v[n-1]) return n-1;
return busca2( x, n-1, v);
}
Busca binária
http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html
Page 2 of 8
Algoritmos: busca binária (versão simplificada)
5/14/13 6:56 PM
Há um método de solução do problema que é muito mais eficiente que a busca sequencial.
Ele se baseia na ideia comumente usada para encontrar um nome em uma lista telefônica. É
claro que a ideia só faz sentido porque o vetor está ordenado.
//
//
//
//
A função abaixo recebe um número x e um vetor
crescente v[0..n-1]. Ela devolve um índice m
tal que v[m] == x ou devolve -1 se tal m não
existe.
int
buscaBinaria( int x, int n, int v[]) {
int e, m, d;
e = 0; d = n-1;
while (e <= d) {
m = (e + d)/2;
if (v[m] == x) return m;
if (v[m] < x) e = m + 1;
else d = m - 1;
}
return -1;
}
Os nomes das variáveis não foram escolhidos por 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 e, d e 2 são do tipo int. Por exemplo, se e e d valem 0 e 5
respectivamente então (e+d)/2 vale 2.
0
e
d
n-1
111 222 333 444 555 555 666 777 888 888 888 999 999
A ideia do algoritmo de busca binária (= binary search) é um verdadeiro "ovo de Colombo".
Ela é a base de muitos algoritmos eficientes para diversos problemas.
Busca binária: a função está correta?
Para compreender o algoritmo, basta verificar que no início de cada repetição do while,
imediatamente antes da comparação de e com d, temos a seguinte relação invariante:
v[e-1]
< x < v[d+1] .
Esse invariante vale até mesmo no início da primeira iteração, se imaginarmos que v[-1]
vale −∞ e que v[n] vale +∞. Esse jogo de imaginação faz sentido porque o vetor é
crescente.
O invariante vale, em particular, no início da última iteração, quando e > d (mais
precisamente, e == d+1). Nesse caso, nenhum elemento do vetor é maior que v[e-1] e
menor que v[d+1], pois o vetor é crescente, Essa observação, junto com a relação invariante
acima, garante que x é diferente de todos os elementos de v[0..n-1]. Conclusão: a resposta
http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html
Page 3 of 8
Algoritmos: busca binária (versão simplificada)
-1
5/14/13 6:56 PM
está correta nesse caso.
O valor da diferença d - e diminui a cada iteração (cuidado: isso não é tão óbvio assim!).
Portanto, a menos que tenhamos v[m] == x, a diferença fica negativa no início de alguma
iteração e então a execução do while termina. Isso encerra a análise da correção do
algoritmo.
Busca binária: desempenho do algoritmo
Quanto tempo o algoritmo leva para parar? 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,
n/4. No início da (k+1)-ésima, n/2k. Quando k passar de log2 n, o valor da expressão n/2k
fica menor que 1 e o algoritmo para. Logo, o número de iterações é aproximadamente
lg( n)
no pior caso, sendo lg(n) o piso de log2n. O número de comparações de x com elementos
do vetor é o dobro disso: 2 lg(n) no pior caso.
O consumo de tempo da busca binária é, portanto, proporcional a lg(n). Isso é muito
melhor que o consumo de tempo da busca sequencial, pois lg transforma multiplicações em
somas. Por exemplo, se cada iteração consome 1 microssegundo então uma busca em n
elementos consome lg(n) microssegundos, uma busca em 2n elementos consumirá apenas
lg(n)+1 microssegundos, uma busca em 8n elementos consumirá apenas lg(n)+3
microssegundos e uma busca em 1024 n elementos consumirá apenas lg(n)+10
microssegundos.
Exercícios
3. Responda as seguintes perguntas sobre a função buscaBinaria descrita acima.
a. Que acontece se
b. Que acontece se
c. Que acontece se
= m-1"?
d. Que acontece se
"while (e <= d)" for trocado por "while (e < d)"?
"while (e <= d)" for trocado por "while (e <= d+1)"?
"e = m+1" for trocado por "e = m"? E se for trocado por "e
"d = m-1" for trocado por "d = m" ou por "d = m+1"?
4. Suponha que v[i] = i para cada i. Execute buscaBinaria com n = 9, e com
vários valores de x. Repita o exercício com n = 14 e x = 9. Repita o exercício com
n = 15 e x = 9.
5. Suponha que o vetor v tem 511 elementos e que x não está no vetor. Quantas
comparações a função buscaBinaria fará entre x e elementos do vetor?
6. Se preciso de t segundos para fazer uma busca binária em um vetor com n
elementos, de quando tempo preciso para fazer uma busca em n² elementos?
http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html
Page 4 of 8
Algoritmos: busca binária (versão simplificada)
5/14/13 6:56 PM
7. Confira a validade da seguinte afirmação: quando n+1 é uma potência de 2, a
expressão (e+d) é sempre divisível por 2, quaisquer que sejam v e x.
8. Execute a função buscaBinaria com n = 16. Quais os possíveis valores de m na
primeira iteração? Quais os possíveis valores de m na segunda iteração? Na
terceira? Na quarta?
9. Escreva uma versão da busca binária que procure x em v[0..n]. Escreva outra
versão para v[1..n].
10. A seguinte implementação da busca binária funciona corretamente? Qual o
invariante dessa versão?
e = -1; d = n;
while (e < d-1) {
m = (e + d)/2;
if (v[m] == x) return m;
if (v[m] < x) e = m;
else d = m;
}
return -1;
Que acontece se trocarmos "while (e < d-1)" por "while (e < d)"?
Versão recursiva da busca binária
Para formular uma versão recursiva da busca binária é preciso generalizar ligeiramente o
problema, trocando v[0..n-1] por v[e..d]. Para estabelecer uma ponte entre a
formulação original e a generalizada, vamos usar uma "função-embrulho" buscaBinaria2,
que repassa o serviço para a função recursiva bb.
//
//
//
//
A função abaixo recebe um número x e um vetor
crescente v[0..n-1]. Ela devolve um índice m
em 0..n-1 tal que v[m] == x. Se tal m não existe,
devolve -1.
int
buscaBinaria2( int x, int n, int v[]) {
return bb( x, 0, n-1, v);
}
//
//
//
//
A função bb recebe um número x e um vetor
crescente v[e..d]. Ela devolve um índice m
em e..d tal que v[m] == x. Se tal m não
existe, devolve -1.
int
bb( int x, int e, int d, int v[]) {
if (e > d) return -1;
else {
int m = (e + d)/2;
if (v[m] == x) return m;
if (v[m] < x)
http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html
Page 5 of 8
Algoritmos: busca binária (versão simplificada)
5/14/13 6:56 PM
return bb( x, m+1, d, v);
else
return bb( x, e, m-1, v);
}
}
Qual a "profundidade da recursão" da função bb? Ou seja, quantas vezes bb chama a si
mesma? Resposta: cerca de log2n vezes.
Exercícios
11. Critique a seguinte versão da função bb. A função recebe um número x e um vetor
crescente v[e..d] tal que e ≤ d e promete devolver um índice m em e..d tal que
v[m] == x (ou -1, se tal m não existe).
int bb( int x, int e, int d, int v[]) {
int m;
if (e == d) {
if (v[d] == x) return d;
else return -1;
}
m = (e + d) / 2;
if (v[m] == x) return m;
if (v[m] < x) return bb( x, m+1, d, v);
else return bb( x, e, m-1, v);
}
Mais exercícios
12. VETOR DE STRINGS. Suponha que v[0..n-1] é um vetor de strings em ordem
lexicográfica. Escreva uma função que receba uma string x e devolva um índice m
tal que a string x é igual à string v[m]. Se tal m não existe, a função deve devolver
-1.
13. VETOR DE STRUCTS. Suponha que cada elemento do vetor v[0..n-1] é uma struct
com dois campos: o nome de um aluno e o número do aluno. Suponha que o vetor
está em ordem crescente de números. Escreva uma função de busca binária que
receba o número de um aluno e devolva o seu nome. Se o número não está no
vetor, a função deve devolver a string vazia.
Exercícios: divisão e conquista
http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html
Page 6 of 8
Algoritmos: busca binária (versão simplificada)
5/14/13 6:56 PM
O paradigma da busca binária serve de base para o conhecido "método da divisão e
conquista", que pode ser usado para resolver eficientemente muitos problemas
computacionais.
14. Escreva uma função que receba um vetor inteiro estritamente crescente v[0..n-1]
e devolva um índice i entre 0 e n-1 tal que v[i] == i ; se tal i não existe, a
função deve devolver -1. O seu algoritmo não deve fazer mais que lg(n)
comparações envolvendo elementos de v.
15. Escreva uma função eficiente que receba inteiros positivos k e n e calcule k n.
Quantas multiplicações sua função executa?
16. A seguinte função recursiva pretende encontrar o valor de um elemento máximo de
v[e..d], supondo e ≤ d. (É claro que não estamos supondo que o vetor está
ordenado.)
int max( int e, int d, int v[]) {
if (e == d) return v[d];
else {
int m, maxe, maxd;
m = (e + d)/2;
maxe = max( e, m, v);
maxd = max( m+1, d, v);
if (maxe >= maxd) return maxe;
else return maxd;
}
}
A função está correta? Ela é mais rápida que a versão iterativa arroz-com-feijão?
Quantas vezes a função chama a si mesma?
URL of this site: www.ime.usp.br/~pf/algoritmos/
Last modified: Sun Jan 20 10:24:22 BRST 2013
Paulo Feofiloff
IME-USP
http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html
Page 7 of 8
Algoritmos: busca binária (versão simplificada)
http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html
5/14/13 6:56 PM
Page 8 of 8