Considere a lista L=[3,5,7,10,9,6,4,12,15,20]. 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?

Passo 1

Beleza, vamos lá! A questão nos apresenta uma lista de números: L = [3, 5, 7, 10, 9, 6, 4, 12, 15, 20]. 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 L = [3, 5, 7, 10, 9, 6, 4, 12, 15, 20]. 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:
  1. Primeira Divisão: O meio da lista de 10 elementos está na posição 5 (índice 4), onde temos o número 9.
  2. Comparação: Comparamos 9 com 10. Como 10 é maior que 9, na busca binária tradicional, iríamos para a metade direita da lista.
  3. Próxima Divisão: Agora, consideramos os elementos à direita de 9: [6, 4, 12, 15, 20]. O meio aqui é 12.
  4. Comparação: 12 é maior que 10, então iríamos para a metade esquerda desse subgrupo.
  5. Última Divisão: O único número à esquerda de 12 é 6.
  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.

Exercícios relacionados