Klaus Paiva

Esses dias eu estava pensando comigo mesmo: “a gente vê várias idéias boas e, por não usar na hora em que vimos, acabamos esquecendo…”. Alguém aí lembrou de algoritmos? É, caso típico. =)

Semana passada eu estava vendo um algoritmo em C++ de busca binária. Deixando o C++ um pouco de lado parei para pensar onde eu já havia aplicado esse algoritmo. Qual não foi a minha surpresa em lembrar de um lugar onde faria sentido e eu deixei de usar o algoritmo. A situação? Marcar uma cidade qualquer numa listagem (combo) HTML.

Permita-me ilustrar melhor o cenário. Imagine uma listagem beeeem grande de cidades (nota: arquivo pesado). Como toda boa lista de cidades, ela está ordenada alfabeticamente. Agora, por algum dado motivo, você gostaria de selecionar uma cidade qualquer X dessa listagem. Nota: a lista tem algumas cidades falsas apenas para aumentar o volume de dados.

Intuitivamente você faria um for percorrendo as opções da listagem e marcando a cidade desejada. Em termos de código isso seria:

var maximo = combo.options.length - 1;
for( var i = 0; i < maximo; i++ )
{
  if( combo.options[i].text == cidade )
  {
    combo.selectedIndex = i;
    return;
  }
}

O código acima funciona, só não funciona bem para a nossa listagem tamanho família. Se eu pedir para marcar uma cidade próxima do final da lista, por exemplo Salto, a busca vai demorar pois o for vai percorrer a lista desde a letra A até chegar no S, aí marcando a cidade desejada.

Se explorarmos um pouco mais nossa intuição veremos que podemos usar algo semelhante ao que fazemos pra pesquisar numa lista telefônica. Abro a lista num ponto e verifico se o nome que eu quero está antes ou depois da página que estou vendo. Por exemplo, estou procurando Vitória. Se eu abri na página com nomes próximos de Teobaldo, vou procurar mais pra frente da lista, não adianta eu olhar pra trás. Essa é a vantagem da ordem alfabética, afinal. =)

Em termos de algoritmos podemos usar uma busca binária para expressar esse comportamento. Ou ainda, falando em código:

var esquerda = 0;
var direita = combo.options.length - 1;
var meio;
while( esquerda <= direita )
{
  meio = esquerda + Math.floor( ( direita - esquerda ) / 2 );
  // Javascript consegue comparar strings usando < e >. Ahá!  
  if( combo.options[meio].text < cidade )
  {
    esquerda = meio + 1;
  }
  else if( combo.options[meio].text > cidade )
  {
    direita = meio - 1;
  }
  else
  {
    // é o cara, pode marcar e encerrar a função
    combo.selectedIndex = meio;
    return;
  }
}

Caso ainda não tenha ficado claro pra você, a busca binária funciona bem melhor para este cenário. Ao invés de percorrer a listagem item a item (linearmente), vamos tomar vantagem da organização alfabética e fazer uma pesquisa mais inteligente. =)

Fiz um arquivo de testes que permite, obviamente, testar as duas implementações (nota: arquivo pesado – cuidado com o pé =). Usei a jQuery somente fora dos algoritmos em questão, pra facilitar a manipulação dos eventos.

Como dá pra notar pelo arquivo de testes, a busca binária funciona melhor para a esmagadora maioria dos casos. O que é de se esperar dada a complexidade O(log n) da busca binária ante a complexidade O(n) da busca linear.

E fica o lembrete, até pra mim mesmo, que tal pesquisar um algoritmo mais eficiente da próxima antes de sair implementando qualquer coisa?