Considere a lista
. Use o algoritmo de busca binária para encontrar os elementos a seguir e mostre o andamento do algoritmo passo a passo:
Busque o elemento 20.
Busque o elemento 20.
Passo 1
Beleza, vamos resumir o que tá rolando aqui. Temos uma lista ordenada chamada
e precisamos encontrar o elemento 20 usando o algoritmo de busca binária. A busca binária é uma técnica eficiente para encontrar itens em listas ordenadas, dividindo a lista pela metade a cada etapa. Para resolver isso, vamos precisar entender como identificar o meio da lista e comparar os valores até encontrar o que estamos procurando.
Passo 2
Primeiro, vamos identificar os índices inicial e final da nossa lista. Lembra que em programação, as listas geralmente começam no índice 0.
- Índice Inicial (
): 0 - Índice Final (
): 8 (porque a lista tem 9 elementos, indo de 0 a 8)
Agora, calculamos o índice do meio usando a fórmula:
Então:
O elemento no índice 4 é 12. Agora, comparamos 20 com 12:
- 20 > 12: Isso significa que o elemento que estamos procurando está na metade direita da lista. Então, vamos ajustar nosso índice inicial para continuar a busca nessa parte.
Passo 3
Atualizamos os índices:
- Novo Índice Inicial (
): - Índice Final (
) permanece 8
Calculamos o novo índice do meio:
O elemento no índice 6 é 20. Agora, comparamos 20 com 20:
- 20 = 20: Achei o elemento!
Resposta
Usando a busca binária, encontramos o elemento 20 no índice 6 da lista.