next up previous contents
Next: Usando rotinas de busca Up: Busca Previous: Busca linear   Sumário

Busca binária

Um mecanismo mais eficiente de busca é análogo àquele utilizado ao procurar uma palavra no dicionário. Faz-se uma estimativa da posição aproximada da palavra e abre-se na página estimada. Se a palavra não foi encontrada nessa página, pelo menos sabe-se em que direção buscar, se mais adiante ou mais atrás no dicionário. O processo de estimar a nova página de busca repete-se até que a página com a palavra desejada seja encontrada. Esse mecanismo de busca só é possível porque as palavras estão ordenadas no dicionário. Se o dicionário mantivesse as palavras sem nenhuma ordem, apenas a busca linear seria possível. Da mesma forma, a busca em uma tabela pode ser melhorada se seu conteúdo estiver ordenado.

O algoritmo de busca binária utiliza exatamente esse princípio. No caso, a estimativa que é feita para a posição a ser buscada é a posição mediana do restante da tabela que falta para ser analisado. No início, o restante é a tabela toda; assim, a primeira posição analisada é a entrada no meio da tabela. Se não for a entrada buscada, analisa-se a metade que resta, ou a inferior (se a chave encontrada tem valor maior que a que se busca) ou a superior (em caso contrário). O procedimento assim se repete, até que se encontre a chave buscada ou que a busca se esgote sem encontrar essa chave.

O Algoritmo 2.2 descreve essa forma de busca. Os dois argumentos são, como para o algoritmo de busca linear, a tabela e a chave de busca. Também como no caso anterior, o valor retornado é o valor associado à chave na tabela ou NIL se a chave não for encontrada. As variáveis bot, mid e top referem-se a posições na tabela -- respectivamente o início, o meio e o fim da área da tabela ainda por ser pesquisada.


\begin{Program}
% latex2html id marker 708\begin{algorithm}{binarySearch}{\tex...
...\\
\RETURN \NIL
\end{algorithm}\caption{Busca binária em tabela.}\end{Program}

Uma diferença entre os dois algoritmos de busca apresentados é que neste assume-se que a tabela está ordenada. A manutenção da ordem em uma tabela dá-se através de procedimentos auxiliares de ordenação, uma das áreas relevantes de estudos em estruturas de dados.

As situações especiais que podem ocorrer nesse processamento de busca incluem o tratamento de mais de uma entrada na tabela com a mesma chave e a situação na qual nenhuma entrada é encontrada para a chave. Tais situações devem ser tratadas, em princípio, pela aplicação, que saberá qual ação deve ser tomada em cada um desses casos.


next up previous contents
Next: Usando rotinas de busca Up: Busca Previous: Busca linear   Sumário
Ivan L. M. Ricarte 2003-02-14