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:
- Comparamos pares de elementos adjacentes na lista.
- Se o elemento da esquerda for maior que o da direita, trocamos eles de posição.
- 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]
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:
- Identificamos o elemento do meio da lista.
- 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.
- 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.