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 10.
Busque o elemento 10.
Passo 1
Beleza, o que a gente tem aqui é uma lista ordenada de números:
. A gente vai usar o algoritmo de busca binária pra encontrar o número 10. A busca binária é ótima pra encontrar elementos rapidamente em listas ordenadas, porque ela divide a lista ao meio várias vezes até achar o que queremos. Vamos precisar entender como dividir a lista e comparar os valores.
Passo 2
Primeiro, a gente identifica os índices inicial e final da lista. Aqui, o índice inicial (
) é 0 e o índice final (
) é 8, porque tem 9 elementos na lista.
Passo 3
Agora, a gente calcula o índice do meio. A fórmula é:
Substituindo:
Então, o elemento no índice 4 é 12.
Passo 4
A gente compara o elemento do meio (12) com o que tá procurando (10). Como 10 é menor que 12, isso significa que o 10, se estiver na lista, está na metade esquerda. Então, a gente ajusta o índice final (
) para um a menos que o meio:
Passo 5
Agora, recalculamos o índice do meio com os novos índices:
O elemento no índice 1 é 5.
Passo 6
Comparamos 5 com 10. Como 10 é maior que 5, o 10 deve estar na metade direita dessa parte da lista. Então, ajustamos o índice inicial (
) para um à frente do meio:
Passo 7
Calculamos o novo índice do meio:
O elemento no índice 2 é 7.
Passo 8
Comparamos 7 com 10. Como 10 é maior que 7, ajustamos o índice inicial novamente:
Passo 9
Calculamos mais uma vez o índice do meio:
O elemento no índice 3 é 10.
Resposta
Encontramos o elemento 10 no índice 3 da lista usando busca binária.