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á 1 mês

Sabe a resposta?

Ganhe 10 pts por resposta de qualidade
3 respostas
Professor Gustavo C.
Respondeu há 1 mês
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á 1 mês
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á 1 mês
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.
São Paulo / SP
Graduação: Engenharia Química (UNIFESP - Universidade Federal de São Paulo)
Programação em C
Possuo experiência como professor de cursinho e particular desde os meus 19 anos,e por intermédio da experiência permitiu-me ,perceber como buscar a melhor metodologia para o discente.Sou estudante de Engenharia Química da UNIFESP. Acredito que a ferramenta de maior poder para a transformação de um ...
Oferece aulas online (sala profes)
Oferece aulas presenciais
R$ 70 / aula
Conversar Whatsapp do professor Douglas R. Whatsapp do professor Douglas R. WhatsApp
1ª aula demonstrativa
4 avaliações
Cotia / SP
Graduação: Licencieatura em matemática (Centro Universitários Uninter)
Computação - Algoritmos Programação em C Arduino - Computação Estrutura de dados Computação - Programação Computação - Algoritmos em C Python
Formado na UNICAMP em Ciência da Computação, atualmente cursando Licenciatura em Matemática. Mais de 10 anos de experiência no mercado de trabalho desenvolvendo projetos de impacto internacional em C, C++ e Python com um histórico de clientes como a Editora Abril, Livepass, IBM e Motorola.
Oferece aulas online (sala profes)
Oferece aulas presenciais
R$ 60 / aula
Conversar Whatsapp do professor Everton C. Whatsapp do professor Everton C. WhatsApp
1ª aula demonstrativa
Responde em 12 min
São Paulo / SP
Doutorado: Doutorado em Física Teórica (Instituto de Fisica da USP)
Programação em C Computação - Shell script
Técnico em Química. Bacharel em Física pelo Instituto de Física da USP(IFUSP)/São Paulo. mestre em Física Teórica IFUSP, doutorando em Física pelo IFUSP.
Oferece aulas online (sala profes)
Oferece aulas presenciais
R$ 50 / aula
Conversar Whatsapp do professor Luiz H. Whatsapp do professor Luiz H. WhatsApp
1ª aula demonstrativa
Responde em 5 h e 47 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