Considere a lista
. Esta lista foi acidentalmente corrompida a partir da posição 5 e não está completamente ordenada.
a) Aplique o algoritmo de busca binária para procurar o elemento 10 e descreva o que acontece. O que isso indica sobre a pré-condição para o uso da busca binária?
a) Aplique o algoritmo de busca binária para procurar o elemento 10 e descreva o que acontece. O que isso indica sobre a pré-condição para o uso da busca binária?
Passo 1
Beleza, vamos lá! A questão nos apresenta uma lista de números:
. O enunciado diz que a lista foi corrompida a partir da posição 5, ou seja, os elementos a partir daí não estão em ordem. Nossa missão é usar o algoritmo de busca binária para procurar o número 10 nessa lista e entender o que acontece. Além disso, vamos discutir o que isso nos mostra sobre as pré-condições necessárias para usar a busca binária.
Passo 2
Primeiro, vamos lembrar como funciona a busca binária. Esse método de busca é super eficiente, mas tem uma regra importante: a lista precisa estar ordenada. Ele funciona dividindo a lista ao meio repetidamente para encontrar o elemento desejado, comparando o elemento do meio com o que estamos procurando.
Passo 3
Agora, vamos aplicar a busca binária na nossa lista
. Observamos que a lista deveria estar ordenada, mas a partir da posição 5, os números não seguem uma sequência crescente ou decrescente.
Passo 4
Vamos ver o que acontece passo a passo:
- Primeira Divisão: O meio da lista de 10 elementos está na posição 5 (índice 4), onde temos o número 9.
- Comparação: Comparamos 9 com 10. Como 10 é maior que 9, na busca binária tradicional, iríamos para a metade direita da lista.
- Próxima Divisão: Agora, consideramos os elementos à direita de 9: [6, 4, 12, 15, 20]. O meio aqui é 12.
- Comparação: 12 é maior que 10, então iríamos para a metade esquerda desse subgrupo.
- Última Divisão: O único número à esquerda de 12 é 6.
- Comparação Final: 6 é menor que 10, então iríamos para a direita, mas não há mais elementos para verificar.
Passo 5
Percebemos que o algoritmo não encontrou o número 10, mesmo ele estando presente na lista original. Isso aconteceu porque a lista não estava totalmente ordenada, e a busca binária depende dessa ordenação para funcionar corretamente.
Resposta
A busca binária falha em encontrar o elemento 10 na lista corrompida, indicando que a pré-condição para usar a busca binária é que a lista deve estar completamente ordenada. Sem essa ordenação, o algoritmo não funciona como esperado.