Algoritmo busca binaria

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 uma decisã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 este problema 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ônico contenha 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, se precisarmos 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