Considere mais uma vez o seguinte problema básico:
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 quando n = 0. É claro que toda instância do problema tem solução e toda solução j pertence ao conjunto {1,2,…,n+1}.
As duas soluções a seguir usam a técnica da busca binária para resolver o problema. A primeira é iterativa e a segunda é recursiva.
| Busca-Binária-Iterativa (A, n, x) |
| 1 o p ← 0 |
| 2 o r ← n+1 |
| 3 o enquanto p < r−1 faça |
| 4 oooo q ← ⌊(p+r)/2⌋ |
| 5 oooo se A[q] < x |
| 6 ooooooo então p ← q |
| 7 ooooooo senão r ← q |
| 8 o devolva r |
(Veja definição de piso.) 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 A[0] vale −∞ e A[n+1] vale ∞.) 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. 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 iteraçõ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 para. Logo, o número de iterações é aproximadamente
lg n
(muito menos que as n iterações de uma busca sequencial). Por exemplo, se cada iteração consome 1 microssegundo então uma busca em n elementos consome lg n microssegundos, uma busca em 8n elementos consumirá apenas 3+lg n microssegundos e uma busca em 1024 n elementos consumirá apenas 10+lg n microssegundos.
A solução recursiva do problema de busca começa com um algoritmo-embrulho, ou algoritmo-interface, que repassa o serviço para um algoritmo recursivo.
| Busca-Binária (A, n, x) |
| 1 o devolva B-B-Recurs (A, 0, n+1, x) |
| B-B-Recurs (A, p, r, x) |
| 1 o se p = r−1 |
| 2 oooo então devolva r |
| 3 oooo senão q ← ⌊(p+r)/2⌋ |
| 4 oooo senão se A[q] < x |
| 5 oooo senão ooo então devolva B-B-Recurs (A, q, r, x) |
| 6 oooo senão ooo senão devolva B-B-Recurs (A, p, q, x) |
O que faz o algoritmo B-B-Recurs? O algoritmo recebe um vetor crescente A[p+1 .. r−1] e um número x tal que A[p] < x ≤ A[r] (donde p < r). (Se A[p] ou A[r] não estiverem definidos, imagine que A[p] = −∞ e A[r] = ∞.) O algoritmo devolve um índice j em {p+1,…,r} tal que A[j−1] < x ≤ A[j].
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 B-B-Recurs é 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):
| B-B-Recurs (A, p, r, x) | ||
| 1 o se p = r−1 | 1 | |
| 2 oooo então devolva r | 1 | |
| 3 oooo senão q ← ⌊(p+r)/2⌋ | 1 | |
| 4 oooo senão se A[q] < x | 1 | |
| 5 oooo senão ooo então devolva B-B-Recurs (A, q, r, x) | T(⌈(n−1⌉)/2) | |
| 6 oooo senão ooo senão devolva B-B-Recurs (A, p, q, x) | T(⌊(n−1)/2⌋) |
Segue daí que o tempo de pior caso, T(n), é definido pela recorrência
T(n) = max (T(⌈(n−1)/2⌉) , T(⌊(n−1)/2⌋)) + 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(0) = 2 e
| T(n) = T(⌈(n−1)/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).
Felizmente não precisamos de uma uma fórmula fechada exata para a função T(n) definida pela recorrência (*). Basta obter uma boa cota superior. Um dos exemplos examinados em outra página sugere que T(n) está em Ο(lg n). (Poderíamos recorrer ao "teorema mestre" uma confirmação.) Vou tentar verificar isso mostrando 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−1)/2⌉ ≥ 2 e adote a hipótese de indução T(⌈(n−1)/2⌉) ≤ 8 lg ⌈(n−1)/2⌉ . Então
| T(n) | = | 8 lg ⌈(n−1)/2⌉ + 3 |
| ≤ | 8 lg ((n−1)/2 + 1/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.