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.
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 lá! Você tem que buscar o elemento 10 em uma lista. Isso faz parte do conteúdo de Pesquisa Binária, que é uma técnica eficiente para encontrar elementos em listas ordenadas. Para resolver isso, vamos precisar identificar os índices inf (inferior), sup (superior), meio (meio) e o valor no meio da lista L[meio] em cada passo até encontrar o elemento ou concluir que ele não está presente.
Passo 2
Primeiro, vamos imaginar que temos uma lista ordenada. Por exemplo:
Os índices dessa lista vão de 0 a 6.
-
inf (inferior) começa no índice 0.
-
sup (superior) começa no índice 6.
-
Calculamos meio como a média de inf e sup:
-
O valor no meio, L[meio], é 8.
Passo 3
Agora, comparamos o valor que estamos buscando (10) com L[3] = 8.
-
Como 10 > 8, sabemos que o elemento, se existir, está na parte direita da lista.
-
Então, atualizamos inf para meio + 1 = 4.
-
sup permanece em 6.
-
Calculamos o novo meio:
-
O valor no meio agora é L[5] = 12.
Passo 4
Comparamos 10 com L[5] = 12.
-
Como 10 < 12, sabemos que o elemento está na parte esquerda da sublista atual.
-
Atualizamos sup para meio - 1 = 4.
-
inf permanece em 4.
-
Calculamos o novo meio:
-
O valor no meio agora é L[4] = 10.
Passo 5
Agora, comparamos 10 com L[4] = 10.
- Achamos o elemento! 10 = 10.
- Portanto, o elemento 10 está na posição 4 da lista.
Resposta
O elemento 10 foi encontrado na posição 4 da lista após 3 passos.