Busca binaria

Computação Algoritmos Estrutura de dados

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

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

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.

Douglas R.

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

R$ 70 / aula

Conversar

1ª aula demonstrativa

4 avaliações

Everton C.

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.

R$ 60 / aula

Conversar

1ª aula demonstrativa

Responde em 12 min

Luiz H.

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.

R$ 50 / aula

Conversar

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

Últimas dúvidas de Computação Pesquisa operacional programação linear Função matricial ou proc avançado Uma tecla remetia a outra Impressora/ internet Data do eixo - grafico excel Formula se Selecionado apenas certas linhas.

Disciplinas principais

Matemática Física Química Biologia Engenharia Cálculo Português

Dúvidas de artes

Desenho Arte Digital História da Arte Teatro Fotografia Artes Plásticas Pintura Gastronomia / Culinária Artesanato Maquiagem Costura Mágica / Ilusionismo Origami

Dúvidas de biológicas

Biologia Farmácia-Bioquímica Medicina Enfermagem Educação Física Nutrição Veterinária Fisioterapia Odontologia Zootecnia Fonoaudiologia

Dúvidas de comportamento

Coaching Alfabetização Comunicação Meditação Etiqueta Astrologia

Dúvidas de dança

Forró Samba Tango FitDance Kizomba

Dúvidas de esportes

Personal Trainer Xadrez Yoga Futebol Vôlei Corrida Basquete Boxe Teoria dos Esportes Tai Chi Chuan

Dúvidas de exatas

Matemática Física Química Cálculo Engenharia Computação Matemática Financeira Estatística Ciências da Terra

Dúvidas de humanas

História Redação Português Geografia Literatura Filosofia Letras Sociologia Pedagogia Administração Direito Economia Ciências Sociais Ciências Contábeis Psicologia Antropologia Marketing Design Arquitetura Jornalismo

Dúvidas de idiomas

Inglês Espanhol Português para estrangeiros Francês Alemão Italiano Japonês Chinês Russo Libras Árabe Latim Coreano Hebraico Holandês Outros idiomas Esperanto Finlandês

Dúvidas de informática

Informática Geral Excel Word PowerPoint Windows Web Design HTML Redes Sociais Redes de Computadores JavaScript SEO

Dúvidas de música

Violão Teoria Musical Canto Guitarra Violino Clarinete Zabumba

Busca binaria

Marcio

Sabe a resposta?

Professor Gustavo C.

Professor Jefferson C.

Professor Alfeu P.

Professores particulares de Computação

Douglas R.

Everton C.

Luiz H.

Pergunte aos nossos professores

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

Disciplinas principais

Dúvidas de artes

Dúvidas de biológicas

Dúvidas de comportamento

Dúvidas de dança

Dúvidas de esportes

Dúvidas de exatas

Dúvidas de humanas

Dúvidas de idiomas

Dúvidas de informática

Dúvidas de música

Conta

Recursos

Sobre o profes