Considere a lista L=[3,5,7,10,9,6,4,12,15,20]. Esta lista foi acidentalmente corrompida a partir da posição 5 e não está completamente ordenada.
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á! O exercício que você me mandou envolve duas partes principais: ordenar uma lista que está meio bagunçada e, depois disso, procurar um número específico nela usando a busca binária. Para resolver isso, a gente vai precisar entender como ordenar uma lista de números e como funciona a busca binária para encontrar elementos de forma eficiente.

Passo 2

Primeiro, vamos ordenar a lista. A lista original é: L = [3,5,7,10,9,6,4,12,15,20]. Ela foi corrompida a partir da posição 5, então os números depois disso estão bagunçados. Para ordenar, vamos usar o método de ordenação por inserção, que é bem intuitivo e fácil de entender.
Ordenação por Inserção:
Esse método funciona pegando cada elemento e colocando ele na posição correta em uma parte já ordenada da lista.
Vamos aplicar isso passo a passo na nossa lista:
  1. Inicio Ordenado: [3]
  2. Adicionar 5: [3, 5] (já está na ordem)
  3. Adicionar 7: [3, 5, 7] (já está na ordem)
  4. Adicionar 10: [3, 5, 7, 10] (já está na ordem)
  5. Adicionar 9: Agora precisamos colocar o 9 na posição correta. A lista ordenada até agora é [3, 5, 7, 10]. O 9 fica entre 7 e 10. Então:
    • [3, 5, 7, 9, 10]
  6. Adicionar 6: A lista é [3, 5, 7, 9, 10]. O 6 fica entre 5 e 7:
    • [3, 5, 6, 7, 9, 10]
  7. Adicionar 4: A lista é [3, 5, 6, 7, 9, 10]. O 4 fica entre 3 e 5:
    • [3, 4, 5, 6, 7, 9, 10]
  8. Adicionar 12: Já está na ordem:
    • [3, 4, 5, 6, 7, 9, 10, 12]
  9. Adicionar 15: Já está na ordem:
    • [3, 4, 5, 6, 7, 9, 10, 12, 15]
  10. Adicionar 20: Já está na ordem:
    • [3, 4, 5, 6, 7, 9, 10, 12, 15, 20]
Agora a lista está totalmente ordenada: Lordenada = [3, 4, 5, 6, 7, 9, 10, 12, 15, 20].

Passo 3

Agora, vamos buscar o elemento 9 usando a busca binária. A busca binária é eficiente porque reduz pela metade o número de elementos a serem verificados a cada passo, mas isso só funciona em listas que já estão ordenadas, o que a gente acabou de fazer.
Como funciona a busca binária:
  1. Identificar o meio da lista.
  2. Comparar o elemento do meio com o que estamos procurando (9):
    • Se for igual, achamos o elemento!
    • Se for maior, repetimos a busca na metade esquerda.
    • Se for menor, repetimos na metade direita.
  3. Repetir esse processo até encontrar o elemento ou concluir que ele não está na lista.
Vamos aplicar isso na nossa lista ordenada:
Lordenada = [3, 4, 5, 6, 7, 9, 10, 12, 15, 20]
  1. Primeira comparação:
    • Meio da lista: posição 5 (índice 4), que é o número 7.
    • 9 > 7, então vamos procurar na metade direita: [9, 10, 12, 15, 20].
  2. Segunda comparação:
    • Meio da nova sublista: posição 3 da sublista (índice 7 da lista original), que é o número 12.
    • 9 < 12, então vamos procurar na metade esquerda dessa sublista: [9, 10].
  3. Terceira comparação:
    • Meio da nova sublista: posição 1 da sublista (índice 5 da lista original), que é o número 9.
    • 9 = 9, encontramos o elemento!
Então, o número 9 está na posição 6 da lista ordenada.

Resposta

Após ordenar, a lista fica L = [3, 4, 5, 6, 7, 9, 10, 12, 15, 20] e o elemento 9 está na posição 6.

Exercícios relacionados