Escreva um algoritmo para corrigir a lista L, deixando-a completamente ordenada. Depois, encontre o elemento 9 usando a busca binária e descreva os passos do algoritmo.

Passo 1

Beleza, vamos lá! A questão pede para a gente criar um algoritmo que organiza uma lista chamada L em ordem crescente. Depois disso, a gente precisa encontrar o número 9 usando a busca binária. Para fazer isso, vamos precisar entender dois conceitos principais: algoritmos de ordenação e busca binária. Não se preocupe, vou explicar tudo passo a passo!

Passo 2

Primeiro, vamos ordenar a lista L. Existem vários métodos para fazer isso, mas vou usar o Método da Bolha (Bubble Sort) porque é simples de entender.
Como funciona o Bubble Sort:
  1. Comparamos pares de elementos adjacentes na lista.
  2. Se o elemento da esquerda for maior que o da direita, trocamos eles de posição.
  3. Repetimos esse processo até que não sejam necessárias mais trocas, ou seja, a lista está ordenada.
Exemplo:
Suponha que L = [5, 3, 8, 4, 2]
  • Primeira passagem:
    • Compare 5 e 3 → troca → [3, 5, 8, 4, 2]
    • Compare 5 e 8 → fica [3, 5, 8, 4, 2]
    • Compare 8 e 4 → troca → [3, 5, 4, 8, 2]
    • Compare 8 e 2 → troca → [3, 5, 4, 2, 8]
  • Segunda passagem:
    • Compare 3 e 5 → fica [3, 5, 4, 2, 8]
    • Compare 5 e 4 → troca → [3, 4, 5, 2, 8]
    • Compare 5 e 2 → troca → [3, 4, 2, 5, 8]
  • Terceira passagem:
    • Compare 3 e 4 → fica [3, 4, 2, 5, 8]
    • Compare 4 e 2 → troca → [3, 2, 4, 5, 8]
  • Quarta passagem:
    • Compare 3 e 2 → troca → [2, 3, 4, 5, 8]
Agora a lista está ordenada: [2, 3, 4, 5, 8]

Passo 3

Agora que a lista está ordenada, vamos buscar o número 9 usando a Busca Binária. Esse método é eficiente porque reduz o intervalo de busca pela metade a cada passo.
Como funciona a Busca Binária:
  1. Identificamos o elemento do meio da lista.
  2. Comparamos o elemento do meio com o número que estamos procurando (neste caso, 9).
    • Se for igual, encontramos o número!
    • Se 9 for maior, repetimos a busca na metade direita da lista.
    • Se 9 for menor, repetimos na metade esquerda.
  3. Repetimos esse processo até encontrar o número ou concluir que ele não está na lista.
Aplicando na nossa lista [2, 3, 4, 5, 8]:
  • Primeira comparação:
    • Meio da lista: 4 (posição 3)
    • 9 é maior que 4 → vamos para a metade direita: [5, 8]
  • Segunda comparação:
    • Meio da nova sublista: 5 (posição 4)
    • 9 é maior que 5 → vamos para a metade direita: [8]
  • Terceira comparação:
    • Meio da nova sublista: 8 (posição 5)
    • 9 é maior que 8 → vamos para a metade direita, mas não há mais elementos.
Como não encontramos o número 9 na lista, concluímos que ele não está presente.

Resposta

Após ordenar a lista L usando o Método da Bolha, ficou assim: [2, 3, 4, 5, 8]. Ao realizar a busca binária pelo número 9, constatamos que ele não está presente na lista.

Exercícios relacionados