You can edit almost every page by Creating an account. Otherwise, see the FAQ.

Pesquisa binária em sequências de intervalo desconhecido

Fonte: EverybodyWiki Bios & Wiki


Esta página foi marcada para revisão, devido a incoerências e/ou dados de confiabilidade duvidosa (desde dezembro de 2009). Se tem algum conhecimento sobre o tema, por favor, verifique e melhore a coerência e o rigor deste artigo.

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:

  1. Supondo que o elemento procurado seja e a sequência ordenada de tamanho desconhecido,
  2. Procura o elemento , que seja maior ou igual que ;
  3. 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:

  1. Para localizar o elemento aplica busca binária no intervalo encontrado;
  2. A complexidade da segunda parte é , pois o intervalo é de tamanho , já que

Ver também[editar]

Portal 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


Ícone de esboço Este sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.


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.



Read or create/edit this page in another language[editar]