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.
Exercícios relacionados
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).
Você pode supor que os valores lidos são todos inteiros (o seu programa deve funcionar corretamente apenas nesse caso).
Escreva um algoritmo que leia 5 valores inteiros e retorna verdadeiro, se e somente se, o conjunto formado pelos 2 últimos números é um subconjunto daquele formado pelos 3 primeiros.
Você pode supor que os valores lidos são todos inteiros (o seu programa deve funcionar corretamente apenas nesse caso).
Você pode supor que os valores lidos são todos inteiros (o seu programa deve funcionar corretamente apenas nesse caso).
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.
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.
Para cada tentativa de inserção, explique como o algoritmo lida com a duplicidade e com o limite de capacidade.