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

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 $z$ e $X$ a sequência ordenada de tamanho desconhecido,
2. Procura o elemento $X[i]$, que seja maior ou igual que $z$;
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 $O(log_{2}(j)$, 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 é $O(log_{2}(j)$, pois o intervalo é de tamanho $j$, já que $2*j-j=j$

Ver também

A Wikipédia tem o portal: Portal das tecnologias de informação

{{#ask: [[Topic::Tecnologias de informação]] [[Topic::{{{2}}}]] [[Topic::{{{3}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |searchlabel=|order=random|limit=7|intro=
Outros artigos dos temas Tecnologias de informação E {{{2}}} E {{{3}}}: }}{{#ask: [[Topic::Tecnologias de informação]] [[Topic::{{{2}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |searchlabel=|order=random|limit=7|intro=

Outros artigos dos temas Tecnologias de informação E {{{2}}}: }}{{#ask: [[Topic::Tecnologias de informação]] [[Topic::{{{3}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |searchlabel=|order=random|limit=7|intro=

Outros artigos dos temas Tecnologias de informação E {{{3}}}: }}{{#ask: [[Topic::Tecnologias de informação]] [[Topic::{{{4}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |searchlabel=|order=random|limit=7|intro=

Outros artigos dos temas Tecnologias de informação E {{{4}}}: }}{{#ask: [[Topic::{{{2}}}]] [[Topic::{{{3}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |searchlabel=|order=random|limit=7|intro=

Outros artigos dos temas {{{2}}} E {{{3}}}: }}{{#ask: [[Topic::{{{2}}}]] [[Topic::{{{4}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |searchlabel=|order=random|limit=7|intro=

Outros artigos dos temas {{{2}}} E {{{4}}}: }}{{#ask: [[Topic::{{{3}}}]] [[Topic::{{{4}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |searchlabel=|order=random|limit=7|intro=

Outros artigos dos temas {{{3}}} E {{{4}}}: }}{{#ask: [[Topic::Tecnologias de informação]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |searchlabel=|order=random|limit=7| intro=

Outros artigos do tema Tecnologias de informação : }}{{#ask: [[Topic::{{{2}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |searchlabel=|order=random|limit=7| intro=

Outros artigos do tema {{{2}}} : }}{{#ask: [[Topic::{{{3}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |searchlabel=|order=random|limit=7| intro=

Outros artigos do tema {{{3}}} : }}{{#ask: [[Topic::{{{4}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |searchlabel=|order=random|limit=7| intro=

Outros artigos do tema {{{4}}} : }}{{#ask: [[Topic::{{{5}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |searchlabel=|order=random|limit=7| intro=

Outros artigos do tema {{{5}}} : }}{{#ask: [[Topic::{{{6}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |searchlabel=|order=random|limit=7| intro=

Outros artigos do tema {{{6}}} : }}{{#ask: [[Topic::{{{7}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |order=random |searchlabel=|limit=7| intro=
Outros artigos do tema {{{7}}} : }}{{#ask: [[Topic::{{{8}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |order=random |searchlabel=|limit=7| intro=
Outros artigos do tema {{{8}}} : }}{{#ask: [[Topic::{{{9}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |order=random|searchlabel=|limit=7| intro=
Outros artigos do tema {{{9}}} : }}{{#ask: [[Topic::{{{10}}}]] PageName::!Pesquisa_binária_em_sequências_de_intervalo_desconhecido |order=random |searchlabel=|limit=7| intro=
Outros artigos do tema {{{10}}} : }} {{#set:PageName=Pesquisa_bin%C3%A1ria_em_sequ%C3%AAncias_de_intervalo_desconhecido }}

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.

---

 Facebook Page

 Follow us on Twitter !

Read or create/edit this page in another language

• Pesquisa binária em sequências de intervalo desconhecido in English