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.
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.