Algoritmo busca binaria

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1350 palavras )
  • Download(s) : 0
  • Publicado : 18 de abril de 2012
Ler documento completo
Amostra do texto
Algoritmo para Busca Binária

Vamos falar um pouco sobre métodos de busca que são baseados em uma ordenação linear das chaves (por exemplo, ordem alfabética ou ordem numérica). Depois de comparar o dado argumento K a uma chave Ki no vetor, a busca continua de três diferentes formas, dependendo se K < Ki, K = Ki ou K > Ki. Os métodos de busca sequencial são essencialmente limitados a umadecisão baseada em dois resultados (K = Ki vs. K <> Ki), mas se não ficarmos presos a restrição de acesso sequencial é possível faze uso efetivo de uma relação de ordenação.
Procurando em um Vetor Ordenado
O que você faria se alguém desse a você uma grande lista telefônica e falasse para você encontra o nome do homem cujo número fosse 795-6841? Não há forma melhor de solucionar esteproblema do que usar os método sequencial. (Contudo, um detetive esperto poderia tentar ligar para o número e descobrir que atendia; ou ele poderia ter um amigo na companhia telefônica que tivesse acesso a um catálogo especial que estivesse ordenado pelo número em vez de pelo nome.) O certo é que é muito mais fácil encontrar uma entrada pelo nome em vez de pelo número, embora o catálogo telefônicocontenha todas as informações necessárias em ambos os casos. Quando um grande arquivo deve ser verificado, a procura sequencial está sempre fora de questão, mas uma relação de ordenação simplifica o trabalho enormemente.
Com tantos métodos de ordenação a nossa disposição, teremos poucas dificuldades em colocar um arquivo em ordem a fim de poder realizar uma busca nele convenientemente. É claro, seprecisarmos apenas procurar no vetor uma vez, é mais rápido fazer uma busca sequencial do que realizar uma ordenação completa do arquivo; mas se precisarmos fazer repetidas buscas no mesmo arquivo, será melhor termos ele em ordem. Então vamos nos concentrar agora em métodos que são apropriados para vasculhar um vetor cujas chaves estão em ordem,
K1 < K2 < … < KN,
fazendo acessos aleatóriosàs entradas do vetor. Depois de comparar K com Ki, em um vetor, nós teremos
 
• K < Ki [Ri, Ri+1, ..., RN são eliminados da consideração];
ou
• K = Ki [a procura terminou];
ou
• K > Ki [R1, R2, ..., Ri são eliminados da consideração];
Em cada um desses três casos, um progresso substancial foi feito, a menos que i esteja próximo a uma das extremidades do vetor; é por isto que aordenação leva a um algoritmo eficiente.
Busca Binária: Talvez o primeiro método que pode-se ter em mente é começar a comparar K com a chave do meio do vetor; o resultado desta comparação nos diz qual metade do vetor deve ser vasculhada a seguir, e o mesmo procedimento pode ser usado novamente, comparando K com a chave do meio da metade selecionada, etc. Depois de no máximo aproximadamente log2Ncomparações, teremos encontrado a chave ou teremos estabelecido que ela não está presente. Este procedimento é conhecido algumas vezes como “busca logarítmica” ou “biseção”, mas é mais comumente chamada de busca binária.
Embora a idéia básica da busca binária seja direta, os detalhes podem ser um tanto intrincados, e muitos bons programadores cometem erros nas primeiras vezes que a usam. Uma das formascorretas mais populares do algoritmo usa dois ponteiros, l e u, que indicam os limites inferior e superior correntes para a busca, como mostrado a seguir:
Algoritmo B (Busca Binária). Dado um vetor de registros R1,R2, …, RN cujas chaves estão em ordem crescente K1< K2 < … < KN, este algoritmo procura por um dado argumento K.
B1. [Inicialize.] Ajuste l <- 1, u <- N.
B2. [Pegue ocentro.] (Neste ponto sabemos que se K está no vetor, ele satisfaz Kl <= K <= Ku.) Se u < l, o
algoritmo termina sem sucesso. Do contrário, coloque i <- (l+ u)/2, o ponto central aproximado do vetor.
B3. [Compare.] Se K < Ki, vá para B4; se K > Ki, vá para B5; e se K = Ki, o algoritmo termina com sucesso.
B4. [Ajuste u.] Faça u <- i – 1 e retorne para B2.
B5. [Ajuste l.]...
tracking img