Busca binaria

Computação Geral Geral

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?

Foto de Marcio F.
Marcio perguntou há 5 anos

Sabe a resposta?

Ganhe 10 pts por resposta de qualidade
Responder dúvida
3 respostas
0
votos
Nenhum usuário votou nessa resposta como útil.
Professor Gustavo C.
Identidade verificada
  • CPF verificado
  • E-mail verificado
Respondeu há 5 anos
Melhor resposta
Essa foi a 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.

Envie uma dúvida gratuitamente

Envie sua primeira dúvida gratuitamente aqui no Tira-dúvidas Profes. Nossos professores particulares estão aqui para te ajudar.

0
votos
Nenhum usuário votou nessa resposta como útil.
Professor Jefferson C.
Identidade verificada
  • CPF verificado
  • E-mail verificado
Respondeu há 5 anos
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.
0
votos
Nenhum usuário votou nessa resposta como útil.
Professor Alfeu P.
Identidade verificada
  • CPF verificado
  • E-mail verificado
Respondeu há 5 anos
Essa é para o Batman.... Realmente estou contigo. Boa sorte! :-)

Professores particulares de Computação

+ Ver todos
Encontre professor particular para te ajudar nos estudos
R$ 60 / h
César D.
Mogi Guaçu / SP
César D.
4,9 (787 avaliações)
Horas de aulas particulares ministradas 87 horas de aula
Tarefas resolvidas 955 tarefas resolvidas
Identidade verificada
  • CPF verificado
  • E-mail verificado
1ª hora grátis
Computação - Java Computação - Excel Programação Básica
Graduação: Matemática Aplicada e Computacional (Universidade Estadual de Campinas (UNICAMP))
Faça aulas de matemática, computação e programação em c, c++, java e python.
R$ 80 / h
Josué S.
São Paulo / SP
Josué S.
5,0 (3 avaliações)
Horas de aulas particulares ministradas 5 horas de aula
Identidade verificada
  • CPF verificado
  • E-mail verificado
1ª hora grátis
Introdução à Computação Introdução à Programação Computação e Informática a domicílio
Mestrado: Engenharia de Software (Instituto Nacional de Pesquisas Espaciais)
Aulas de programação, pensamento computacional e gestão de projetos