Busca binaria

Alguém pode me ajudar com a seguinte questão: 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. Márcio whatsapp 15 991028516


Minha duvida é na questão. Não consigo sair dela.


 


Gustavo, como eu falo com vc, não domino a plataforma. Não to vendo um botao aqui. tem com me chamar no whatsapp?

Marcio F.
Marcio
perguntou há 3 meses

Sabe a resposta?

Ganhe 10 pts por resposta de qualidade
3 respostas
Professor Gustavo C.
Respondeu há 3 meses
Melhor resposta
Melhor resposta escolhida pelo autor da dúvida
No algoritmo de busca binária, você precisa saber o limite inferior e o limite superior para fazer a busca.

Antes de fazer a busca binária você precisa calcular esses limites. Então precisa criar um algoritmo novo que chama encontrarLimites. Ele é mais ou menos assim:

encontrarLimite (vetor, chave)
{
inf = 0
sup = 1
while (vetor[sup] < chave)
{
inf = sup
sup = sup * 2
}
return (buscaBinaria (vetor, inf,
sup, chave))
}

Já que a gente não sabe o tamanho do vetor, mas sabe que ele é ordenado, a gente dobra o limite superior até ele passar do valor da chave que estamos procurando. Quando ele passar, sabemos que a chave não está além disso, então colocamos isso como o limite superior da busca binária.

A complexidade desse algoritmo é O(log p), mesmo que da busca binária, sendo que p é o índice da chave que estamos procurando.
Professor Jefferson C.
Respondeu há 3 meses
Via de regra a complexidade de um algoritmo é calculada a partir do número de iterações aninhadas, a grosso modo seria o número de loops aninhados necessários para se alcançar o ponto de parada no pior cenário. A notação utilizada é a O(n). Então, por exemplo, se seu algoritmo irá ter dois loops (for, while, etc...) aninhados e o pior caso seja passar por todos elementos do loop mais externo e para cada ítem externo você também precisa passar por todos elementos do loop interno a sua complexidade seria O(n^2) - lê-se "O de n ao quadrado". Existe muito mais coisa por trás disso, pq a complexidade pode ser logaritmica, cúbica, etc mas isso depende de cada caso. Não analisei o exercício que você colocou mas espero ter ajudado.
Professor Alfeu P.
Respondeu há 3 meses
Essa é para o Batman.... Realmente estou contigo. Boa sorte! :-)

Professores particulares de Computação

+ Ver todos
Encontre e contrate um professor particular para te ajudar nos estudos.
Débora está online
São Paulo / SP
Graduação: Engenharia Química (UFRJ)
Computação e Informática para o Ensino Médio Computação - Bootstrap Geoprocessamento SQL Server Scrum Operador de Microcomputadores Curso Superior em Computação e Informática
Professora formada em Engenharia Química, Vasta experiência em didática, ensino remoto e online para alunos da graduação de todas as engenharias
Oferece aulas online (sala profes)
Oferece aulas presenciais
R$ 90 / aula
Conversar Whatsapp do professor Débora B. Whatsapp do professor Débora B. WhatsApp
1ª aula demonstrativa
Responde em 3 min
São Paulo / SP
MBA: Graduou-se com distinção - Ênfase Finanças e Estratégia (Stephen M. Ross School of Business -Univ. de Michigan )
Computação - Mídias sociais Computação - Criação de Websites[ Word Desenvolvimento de Sites Computação - Programação Estrutura de dados Computação - Windows 10
Mestre em Finanças, Contabilidade, Estatística e Microsoft Office 365 (Excel, Word, Powerpoint. Outlook))
Oferece aulas online (sala profes)
Oferece aulas presenciais
R$ 75 / aula
Conversar Whatsapp do professor Alfeu P. Whatsapp do professor Alfeu P. WhatsApp
1ª aula demonstrativa
1 avaliação
Uberlândia / MG
Mestrado: Física (UFU - UNIVERSIDADE FEDERAL DE UBERLÂNDIA)
Instalação de Linux Computação - Programação Introdução à Lógica de programação Estrutura de dados Computação - Algoritmos Programação em Linguagem Python Linux Iniciante
Olá Pessoal, sou Bacharelando em Física na Universidade Federal de Uberlândia (concluindo). Atualmente participo do grupo de pesquisa em Nanociência no Instituto de Física da UFU. Sou experiente em aulas particulares, lecionei Álgebra Linear e Calculo Diferencial Integral II enquanto estudava Lice ...
Oferece aulas online (sala profes)
Oferece aulas presenciais
R$ 50 / aula
Conversar Whatsapp do professor Renan M. Whatsapp do professor Renan M. WhatsApp
1ª aula demonstrativa
Responde em 3 min

Pergunte aos nossos professores

Você possui uma lista de exercícios ou Trabalho?

Se seu problema for dificuldade em uma lista de exercícios, revisão de teses e dissertações, correção de textos ou outros trabalhos, peça uma ajuda pelo Tarefas Profes.

Enviar Tarefa