Pesquisa binária em sequências de intervalo desconhecido
A pesquisa binária em sequências de intervalo desconhecido é um algoritmo que faz uma busca numa sequência de tamanho indeterminado.
Sequência de passos[editar]
A idéia é encontrar um intervalo onde está o elemento procurado, depois aplicar busca binária a ele.
1. Encontra o intervalo que contém o valor procurado:
- Supondo que o elemento procurado seja e a sequência ordenada de tamanho desconhecido,
- Procura o elemento , que seja maior ou igual que ;
- Para determinar o índice superior, dobramos a cada passo o limite superior do espaço de busca atual. Até que a afirmação abaixo seja verdadeira:
X[j] <= z <= X[2*j];
2. A complexidade desta primeira parte é igual a , onde j é o menor índice para o qual vale
z <= X[2*j];
3. Usa busca binária dentro do intervalo encontrado em 1:
- Para localizar o elemento aplica busca binária no intervalo encontrado;
- A complexidade da segunda parte é , pois o intervalo é de tamanho , já que
Ver também[editar]
A Wikipédia tem o portal: |
Outros artigos do tema Tecnologias de informação : Companhia de Processamento de Dados do Estado de São Paulo, Stock Distribuidora, Master Business Information Systems, MLDonkey, Wi-Fi Protected Access, Sistema setorial, Abante Corporation
Este artigo "Pesquisa binária em sequências de intervalo desconhecido" é da wikipedia The list of its authors can be seen in its historical and/or the page Edithistory:Pesquisa binária em sequências de intervalo desconhecido.