0

Boa Tarde, alguém poderia me ajudar com a disciplina de complexidade de algoritmo, to parado na questão de busca binaria. Algum pode me ajudar com a questão abaixo:

Considere novamente outra variação do problema da pesquisa binária, escreva um algoritmo para resolvê-lo e calcule a sua complexidade. Desta vez a busca se dará em uma seqüência de tamanho desconhecido conforme descrevemos. Dado uma seqüência teoricamente infinita x1 < x2 < x3 < x4 < ... e um elemento z, achar o índice i tal que xi = z.

1
  • Posta pra gente o que você tentou... ;)
    – sbrubes
    Commented 17/03/2019 às 20:29

1 Resposta 1

0

Como se sabe, o algoritmo de busca binária normal trabalha entre dois índices, que inicialmente são o primeiro e o último índices do array.

Como você está trabalhando com um array infinito, não existe "último índice". Assim sendo, precisamos escolher um índice para ser o índice superior, e a partir daí aplicamos a busca binária normal. Este índice não pode ser totalmente arbitrário. É preciso garantir que o elemento procurado não apareça depois do índice escolhido.

Para preservar a complexidade assintótica da busca binária, pode-se usar o seguinte algoritmo para encontrar um índice superior apropriado em um array infinito:

(Considera-se uma linguagem cujos índices começam em 0)

declare o índice inferior, inicialmente com 0
declare o índice superior, inicialmente com 2

enquanto o elemento no índice superior for menor que o elemento procurado
    o índice inferior recebe o índice superior
    o índice superior é dobrado

faça a pesquisa binária normal entre os índices inferior e superior

É muito importante notar que este algoritmo funciona somente se os elementos do array são crescentes, exatamente como exposto na pergunta:

uma seqüência teoricamente infinita x1 < x2 < x3 < x4 < ...

Nem todo array ordenado obedece a essa lei. Por exemplo, um array infinito em que todos os elementos são 1 pode ser considerado ordenado, mas o algoritmo acima vai entrar em loop infinito se o elemento procurado for 2.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .