Welcome to EverybodyWiki ! Nuvola apps kgpg.png Sign in or create an account to improve, watchlist or create an article like a company page or a bio (yours ?)...

Pesquisa binária em sequências de intervalo desconhecido

Fonte: EverybodyWiki Bios & Wiki
Saltar para a navegação Saltar para a pesquisa


Searchtool.svg
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:
  • Portal das tecnologias de informação
  • Portal das tecnologias de informação



Outros artigos do tema Tecnologias de informação : NAP do Brasil, NAT transversal, Exploração do espaço de projeto, YouTube, Google, Sistema setorial, Globolog


Í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.



Compte Twitter EverybodyWiki Follow us on https://twitter.com/EverybodyWiki !