Considere a lista L=[3,5,7,10,12,15,20,25,30]. Use o algoritmo de busca binária para encontrar os elementos a seguir e mostre o andamento do algoritmo passo a passo:
Busque o elemento 20.

Passo 1

Beleza, vamos resumir o que tá rolando aqui. Temos uma lista ordenada chamada L = [3, 5, 7, 10, 12, 15, 20, 25, 30] e precisamos encontrar o elemento 20 usando o algoritmo de busca binária. A busca binária é uma técnica eficiente para encontrar itens em listas ordenadas, dividindo a lista pela metade a cada etapa. Para resolver isso, vamos precisar entender como identificar o meio da lista e comparar os valores até encontrar o que estamos procurando.

Passo 2

Primeiro, vamos identificar os índices inicial e final da nossa lista. Lembra que em programação, as listas geralmente começam no índice 0.
  • Índice Inicial ( inícioí): 0
  • Índice Final ( fim): 8 (porque a lista tem 9 elementos, indo de 0 a 8)
Agora, calculamos o índice do meio usando a fórmula:
meio = lfloor início + fim2 rfloor í
Então:
meio = lfloor 0 + 82 rfloor = 4
O elemento no índice 4 é 12. Agora, comparamos 20 com 12:
  • 20 > 12: Isso significa que o elemento que estamos procurando está na metade direita da lista. Então, vamos ajustar nosso índice inicial para continuar a busca nessa parte.

Passo 3

Atualizamos os índices:
  • Novo Índice Inicial ( inícioí): meio + 1 = 4 + 1 = 5
  • Índice Final ( fim) permanece 8
Calculamos o novo índice do meio:
meio = lfloor 5 + 82 rfloor = lfloor 6.5 rfloor = 6
O elemento no índice 6 é 20. Agora, comparamos 20 com 20:
  • 20 = 20: Achei o elemento!

Resposta

Usando a busca binária, encontramos o elemento 20 no índice 6 da lista.

Exercícios relacionados