Busque o elemento 20.
Para cada item, descreva os valores de inf, sup, meio, e L[meio] em cada passo até encontrar o elemento ou determinar que ele não está na lista.

Passo 1

Beleza, vamos resolver esse exercício juntos! A missão aqui é buscar o elemento 20 em uma lista usando o método de busca binária. Pra isso, precisamos entender alguns conceitos básicos:
  • Busca Binária: É um método eficiente para encontrar um elemento em uma lista ordenada. Ele funciona dividindo a lista ao meio repetidamente até encontrar o elemento ou concluir que ele não está na lista.
  • Variáveis principais:
    • inf (inferior): Representa o índice inicial da parte da lista que estamos considerando.
    • sup (superior): Representa o índice final da parte da lista que estamos considerando.
    • meio: É o índice central entre inf e sup.
    • L[meio]: É o valor no índice meio da lista.
Antes de começar, precisamos de uma lista ordenada para realizar a busca. Vamos supor que nossa lista L seja a seguinte:
L = [3, 7, 12, 15, 20, 22, 27, 30, 35, 40]

Passo 2

Primeiro, vamos definir os valores iniciais:
  • inf = 0 (começamos no primeiro índice)
  • sup = 9 (último índice da lista, já que ela tem 10 elementos)
  • Calculamos o meio:
    meio = lfloor inf + sup2 rfloor = lfloor 0 + 92 rfloor = 4
  • Então, L[meio] = L[4] = 20
Agora, comparamos L[meio] com o elemento que estamos buscando, que é 20.

Passo 3

Vamos comparar agora:
  • L[meio] = 20
  • Elemento buscado = 20
Como L[meio] é igual ao elemento que estamos procurando, encontramos o elemento na posição 4 da lista.

Resposta

Encontramos o elemento 20 na posição 4 da lista.

Exercícios relacionados