Como encontrar um dado CPF numa longa lista de números de CPF? Se a lista não estiver ordenada, não há o que fazer senão percorrer a lista toda. Se a lista estiver ordenada, entretanto, é possível fazer algo bem melhor. Esse problema é um caso particular do seguinte
Problema da busca em vetor ordenado: Dado um inteiro x e um vetor inteiro crescente A[1 .. n], encontrar j tal que A[j−1] < x ≤ A[j].
O problema faz sentido para todo n natural, até mesmo para n = 0. Toda instância do problema tem solução e toda solução j pertence ao intervalo 1 .. n+1. Se x > A[n], por exemplo, então n+1 é a resposta correta. (Veja o exemplo de Busca em vetor ordenado em outra página.)
O seguinte algoritmo iterativo é uma solução muito eficiente do problema da busca em vetor ordenado:
| Busca-Binária-Iterativa (A, n, x) |
| 1 . p := 0 |
| 2 . r := n+1 |
| 3 . enquanto p < r−1 |
| 4 .ooo q := ⌊(p+r)/2⌋ |
| 5 .ooo se A[q] < x |
| 6 .oooooo p := q |
| 7 .ooo senão r := q |
| 8 . devolva r |
No início de cada repetição do enquanto
,
imediatamente antes da comparação de p com r−1,
vale a relação
A[p] < x ≤ A[r].
(Imagine que o vetor tem um elemento A[0] com valor −∞ e um elemento A[n+1] com valor +∞.) Como essa relação vale no início de cada iteração, dizemos que ela é invariante. (Note a semelhança entre esta relação e o objetivo que estamos perseguindo.) É óbvio que r é a resposta correta quando p = r−1.
Em cada iteração temos p < q < r no fim da linha 4. Logo, tanto r−q quanto q−p são (estritamente) menores que r−p. Portanto, a sequência de valores da expressão r−p é estritamente decrescente. Assim, o número de iterações é finito.
O consumo de tempo de Busca-Binária-Iterativa é proporcional a número de repetições do bloco de linhas 4 a 7. Qual é esse número?
No início da primeira iteração, r−p 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 atinge ou ultrapassa lg n, o valor da expressão n/2k fica menor ou igual a 1 e a execução do algoritmo termina. Logo, o número de iterações é aproximadamente
lg n .
(Isso é muito menos que as n iterações de uma busca sequencial.) Se cada iteração consome 1 unidade de tempo então uma busca em n elementos consome lg n unidades de tempo, uma busca em 8n elementos consumirá apenas 3 + lg n unidades de tempo, e uma busca em 1024 n elementos consumirá apenas 10 + lg n unidades de tempo.
A solução recursiva do problema de busca começa com um algoritmo-embrulho (= wrapper function), ou algoritmo-interface, que repassa o serviço para o algoritmo recursivo propriamente dito.
| Busca-Binária (A, n, x) |
| 1 . devolva BB-r (A, 0, n+1, x) |
| BB-r (A, p, r, x) |
| 1 . se p = r−1 |
| 2 .ooo devolva r e pare |
| 3 . q := ⌊(p+r)/2⌋ |
| 4 . se A[q] < x |
| 5 .ooo devolva BB-r (A, q, r, x) |
| 6 . senão devolva BB-r (A, p, q, x) |
O sufixo -r
é uma abreviatura de recursivo
.)
O algoritmo BB-r
recebe um vetor crescente A[p+1 .. r−1]
e um número x tal que A[p] <
x ≤
A[r]
(portanto p < r)
e devolve um índice j no intervalo p+1 .. r
tal que A[ j−1] <
x ≤ A[ j].
(Imagine que A[p] = −∞ e A[r] = +∞.)
A prova de que o algoritmo de fato produz um tal j procede por indução em r−p. Se r−p = 1 então o algoritmo devolve r e esta é a resposta correta pois p = r−1 e A[p] < x ≤ A[r]. Suponha agora que r−p > 1. Nossa hipótese de indução é que o algoritmo produz a resposta correta quando invocado com argumentos (A, p′, r′, x) tais que r′−p′ < r−p. Em particular, o algoritmo produz a resposta correta quando invocado com argumentos (A, q, r, x) e (A, p, q, x).
O consumo de tempo do algoritmo BB-r
é função do número de elementos, digamos n,
do vetor A[p+1 .. r−1].
É claro que n = r−p−1.
Digamos que o algoritmo consome T(n) unidades de tempo
no pior caso.
Para calcular T(n),
considere o consumo de tempo de cada linha do algoritmo
(supondo que cada linha simples
consome
uma unidade de tempo):
| BB-r (A, p, r, x) | ||
| 1 . se p = r−1 | 1 | |
| 2 .ooo devolva r e pare | 1 | |
| 3 . q := ⌊(p+r)/2⌋ | 1 | |
| 4 . se A[q] < x | 1 | |
| 5 .ooo devolva BB-r (A, q, r, x) | T(⌊n/2⌋) | |
| 6 . senão devolva BB-r (A, p, q, x) | T(⌈n/2⌉ − 1) |
(Para entender o ⌊n/2⌋
e o ⌈n/2⌉ − 1
nas linhas 5 e 6,
veja o exercício abaixo.)
Segue daí que o tempo de pior caso, T(n),
é definido pela recorrência
T(n) = max (T(⌊n/2⌋), T(⌈n/2⌉ − 1)) + 3
para n = 1, 2, 3, etc., com valor inicial T(0) = 2. (Puxa! que complicado!) A intuição sugere que T(n) cresce com n. Suporemos então que
| T(n) = T(⌊n/2⌋) + 3 | (*) |
para n = 1, 2, 3, etc. Eis alguns valores:
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| T(n) | 2 | 5 | 8 | 8 | 11 | 11 | 11 | 11 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 17 | 17 |
Resta extrair daí uma fórmula fechada para T(n).
Solução da recorrência. Felizmente não precisamos de uma fórmula fechada exata para a função T(n) definida pela recorrência (*). Basta obter uma boa cota superior. O exemplo B da página Recorrências sugere que T(n) = Ο(lg n). Poderíamos recorrer ao Teorema Mestre para uma confirmação, mas prefiro mostrar diretamente que
T(n) ≤ 8 lg n
para n = 2, 3, 4, etc. (Não há mal em ignorar os casos em que n vale 0 ou 1.) A desigualdade é evidentemente verdadeira quando n = 2 e n = 3. Agora suponha que n > 3. Observe que ⌊n/2⌋ ≥ 2 e adote a hipótese de indução T(⌊n/2⌋) ≤ 8 lg ⌊n/2⌋. Então
| T(n) | = | 8 lg ⌊n/2⌋ + 3 |
| ≤ | 8 lg (n/2) + 3 | |
| = | 8 (lg n − 1) + 3 | |
| = | 8 lg n − 8 + 3 | |
| < | 8 lg n . |
Viva! Isso prova o que queríamos.
Não é difícil provar, de maneira semelhante, que T(n) ≥ lg n para n = 1, 2, 3, etc.
A[q] < xna linha 4 de BB-r. (A função N é relevante porque o consumo de tempo de BB-r é proporcional a N(n). Assim, N tem o mesmo papel que a função T acima.) Escreva a recorrência que define N(n). Mostre que N(n) ≤ 8 lg n para n = 2, 3, 4, etc. Mostre que N(n) ≥ lg n para n = 2, 3, 4, etc.