Considere a lista L=[3,5,7,10,12,15,20,25,30]. 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.

Passo 1

Beleza, o que a gente tem aqui é uma lista ordenada de números: L=[3,5,7,10,12,15,20,25,30]. 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 ( esquerda) é 0 e o índice final ( direita) é 8, porque tem 9 elementos na lista.

Passo 3

Agora, a gente calcula o índice do meio. A fórmula é:
meio = lfloor esquerda + direita2 rfloor
Substituindo:
meio = lfloor 0 + 82 rfloor = 4
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 ( direita) para um a menos que o meio:
direita = 4 - 1 = 3

Passo 5

Agora, recalculamos o índice do meio com os novos índices:
meio = lfloor 0 + 32 rfloor = 1
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 ( esquerda) para um à frente do meio:
esquerda = 1 + 1 = 2

Passo 7

Calculamos o novo índice do meio:
meio = lfloor 2 + 32 rfloor = 2
O elemento no índice 2 é 7.

Passo 8

Comparamos 7 com 10. Como 10 é maior que 7, ajustamos o índice inicial novamente:
esquerda = 2 + 1 = 3

Passo 9

Calculamos mais uma vez o índice do meio:
meio = lfloor 3 + 32 rfloor = 3
O elemento no índice 3 é 10.

Resposta

Encontramos o elemento 10 no índice 3 da lista usando busca binária.

Exercícios relacionados