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á 3 meses

Sabe a resposta?

Ganhe 10 pts por resposta de qualidade

3 respostas

Professor Gustavo C.

Respondeu há 3 meses

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

Débora B.

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

R$ 90 / aula

Conversar

1ª aula demonstrativa

Responde em 3 min

Alfeu P.

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

R$ 75 / aula

Conversar

1ª aula demonstrativa

1 avaliação

Renan M.

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

R$ 50 / aula

Conversar

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

Últimas dúvidas de Computação Contadores - sistemas digitais Lógica para computação - simples, mas me atrapalho.... Agentes lógicos em prolog - bem simples - mas não consigo Enviar emails no excel (macro) Rede hierárquica Somar por formatação condicional Exercicio vetores

Disciplinas principais

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

Dúvidas de artes

Desenho História da Arte Arte Digital 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 Tai Chi Chuan Teoria dos Esportes

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 Teologia 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 CSS 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

Débora B.

Alfeu P.

Renan M.

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