"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 seqüencial

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;
   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 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 microsegundo decorre entre duas comparações consecutivas, então uma busca em n elementos consome n microsegundos e uma busca em 8n elementos consome 8n microsegundos.

É 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 do problema que é muito mais eficiente que a busca seqüencial. Ele se baseia na idéia comumente usada para encontrar um nome em uma lista telefônica.  É claro que a idéia 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 idéia 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] .

Essa 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.

A invariante vale, em particular, se tivermos  e = d+1  no início de uma iteração. Nesse caso, é evidente que não existe um número inteiro que seja maior que v[e-1] e menor que v[d+1].  Essa observação, junto com a relação invariante acima, mostra que x é diferente de todos os elementos de v[0..n-1].  Conclusão: a resposta -1 está correta nesse caso.

Resta verificar que a execução do processo pára mais cedo ou mais tarde.  Observe que o valor da diferença  d - e  diminui a cada iteração  (cuidado: isso não é tão óbvio assim!).  Portanto, a diferença fica negativa mais cedo ou mais tarde e então o algoritmo pára,

Busca binária: desempenho do algoritmo

Quanto tempo o algoritmo leva para parar? Na início da primeira iteração, d-e vale aproximadamente n. Na início da segunda, vale aproximadamente n/2. Na início da terceira, n/4. Na início da (k-1)-ésima, n/2^k.  Quando k passar de log₂n, o valor da expressão n/2^k fica menor que 1 e o algoritmo pára. Logo, o número de iterações é aproximadamente

lg (n)

no pior caso, sendo lg(n) nossa notação para o piso de log₂n. 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 seqüencial, pois lg transforma multiplicações em somas. Por exemplo, se cada iteração consome 1 microsegundo então uma busca em n elementos consome lg(n) microsegundos, uma busca em 2n elementos consumirá apenas lg(n)+1 microsegundos, uma busca em 8n elementos consumirá apenas lg(n)+3 microsegundos e uma busca em 1024 n elementos consumirá apenas lg(n)+10 microsegundos.

Exercícios

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)  
         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 log₂n vezes.

Exercícios

Mais exercícios

Exercícios: divisão e conquista