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:

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:
  • 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

Busque o elemento 10.
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.
Escreva um algoritmo que, dados três números inteiros, retorna verdadeiro, se e somente se, os números podem representar lados de um triângulo retângulo.
Você pode supor que os valores lidos são todos inteiros (o seu programa deve funcionar corretamente apenas nesse caso).
a) Tente inserir o elemento 10 e descreva cada passo do algoritmo.
Para cada tentativa de inserção, explique como o algoritmo lida com a duplicidade e com o limite de capacidade.
Busque o elemento 8.
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.