"Binary search is to algorithms what a wheel is to mechanics:
It is simple, elegant, and immensely important."
—Udi Manber, Introduction to Algorithms

"A good algorithm is like a sharp knife:
it does what it is supposed to do with a minimum amount of applied effort.
Using the wrong algorithm to solve a problem is like trying to cut a steak with a screwdriver:
you may eventually get a digestible result,
but you will expend considerably more effort than necessary,
and the result is unlikely to be aesthetically pleasing."
—Th. Cormen, Ch. Leiserson, R. Rivest, 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  j  tal que  v[j] == x .

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.  Veja também os capítulos 4 e 5 do "Programming Pearls".

Decisões de projeto

Comecemos por tornar o problema um pouco mais elaborado:  vamos exigir que o algoritmo devolva j tal que

v[j-1]   <   x   ≤   v[j] .

Assim, o usuário ficará sabendo onde x está — basta comparar x com v[j] — ou onde deveria estar.  Para que a coisa fique completa, devemos permitir que j valha  0  ou  n.  Nesses casos a condição acima deve ser interpretada com inteligência:  se j == 0 então a condição se reduz a

x   ≤   v[0] ,

pois v[-1] não faz sentido;  se j == n então a condição se reduz a

v[n-1]   <   x ,

pois v[n] não faz sentido. Tudo se passa como se nosso vetor tivesse um componente imaginário v[-1] com valor infinito negativo e um componente imaginário v[n] com valor infinito positivo.

No exemplo abaixo, se x vale 555 então o valor correto de j é 4. Se x vale 1000 então o valor correto de j é 13.

0												n-1
111	222	333	444	555	555	666	777	888	888	888	999	999

Precisamos tomar mais uma decisão de projeto: qual o menor vetor com que vamos nos preocupar?  Suporemos sempre que

n ≥ 1,

pois isso torna o raciocínio mais simples. É verdade, entretanto, que o problema faz sentido mesmo quando n vale 0  (a solução do problema é necessariamente 0 nesse caso).

Busca sequencial

Comecemos com um algoritmo simples e óbvio:

int 
busca (int x, int n, int v[]) {
   int j = 0;
   while (j < n && v[j] < x) ++j;
   return j;
}

Quantas comparações de x com elementos de v essa função faz? A resposta é

n   no pior caso.

É 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

Busca binária

Há um método de solução muito mais eficiente para nosso problema. Ele se baseia no método que todos nós usamos 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 vetor crescente v[0..n-1] 
// com n >= 1 e um número x. Ela 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, m, d;
   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) { 
      m = (e + d)/2; 
      if (v[m] < x) e = m;
      else d = m;
   }
   return d;
}

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 3 e 6 respectivamente então (e+d)/2 vale 4.

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:

v[e]   <   x   ≤   v[d] .

(Confira!)  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 a relação v[j-1] < x ≤ v[j] que é o objetivo que estamos perseguindo.)  É óbvio que d é a resposta correta quando e == d-1.

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 o algoritmo para mais cedo ou mais tarde.

Busca binária: desempenho da função

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/2^k. Quando k atinge ou ultrapassa log₂ n, o valor da expressão n/2^k fica menor ou igual a 1 e o algoritmo para. Logo, o número de iterações é aproximadamente

lg (n) ,

o que é muito melhor que as n iterações da 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.

Exercícios

Busca binária: uma versão mais limpa

É fácil perceber que os testes iniciais, antes do while, podem ser substituídos por uma inicialização apropriada de e e d:

// Esta função recebe um vetor crescente v[0..n-1]
// com n >= 1 e um número x. Ela devolve um índice
// j em 0..n tal que v[j-1] < x <= v[j].

int 
buscabinaria2 (int x, int n, int v[]) { 
   int e, m, d; 
   e = -1; d = n; 
   while (e < d-1) {
      m = (e + d)/2;
      if (v[m] < x) e = m;
      else d = m; 
   }
   return d;
}

No início de cada repetição do while, imediatamente antes da comparação de e com d-1, vale a propriedade invariante

v[e]  <  x  ≤  v[d]  ,

como já vimos acima.  Esta propriedade é a chave do algoritmo; o algoritmo foi construído em torno desta propriedade. No início da primeira iteração, a propriedade está automaticamente satisfeita, pois v[-1] e v[n] não fazem sentido. (Não está convencido? Então imagine que v[-1] vale infinito negativo e v[n] vale infinito positivo.)

Exercícios

Mais exercícios

Versão recursiva da busca binária

A formulação do problema que usamos até agora não é apropriada para uma solução recursiva. É preciso generalizar a formulação. Para estabelecer uma ponte entre a formulação original e a generalizada, vamos usar uma "função-embrulho" buscabinaria3, que trata dos casos triviais e repassa todo o serviço pesado para a função recursiva bb.

// A função abaixo recebe um vetor crescente v[0..n-1] 
// com n >= 1 e um número x. Ela devolve um índice j
// em 0..n tal que v[j-1] < x <= v[j].

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);
}

A função recursiva bb resolve um problema mais geral: em vez de fazer uma busca em v[0..n-1], ela faz a busca em v[e..d], com e variável.

// Esta função recebe um vetor crescente v[e+1..d-1] e um 
// número x tal que v[e] < x <= v[d] (portanto, e < d).
// Ela devolve um índice j em e+1..d tal que
// v[j-1] < x <= v[j].

int 
bb (int x, int e, int d, int v[]) {
   if (e == d-1) return d;    // base da recursão
   else {
      int m = (e + d)/2;
      if (v[m] < x)  
         return bb (x, m, d, v);
      else  
         return bb (x, e, m, v); 
   } 
}

Qual a "profundidade da recursão" da função bb?  Ou seja, quantas vezes bb chama a si mesma? Resposta: cerca de log₂n vezes.

Exercícios

Mais exercícios

Divisão e conquista