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á! O enunciado pede para a gente aplicar o algoritmo de busca binária para procurar o número 10 e descrever o que acontece. Além disso, temos que explicar o que isso mostra sobre as condições necessárias para usar a busca binária. Para resolver isso, vamos precisar entender como funciona a busca binária e ter uma lista de números ordenada onde vamos procurar o 10.

Passo 2

Primeiro, vamos relembrar o que é busca binária. É um método eficiente para encontrar um elemento em uma lista ordenada. A ideia é dividir a lista ao meio repetidamente até encontrar o elemento desejado ou concluir que ele não está na lista. Para isso, é essencial que a lista esteja ordenada, porque a busca binária se baseia nessa ordenação para descartar metade da lista a cada passo.

Passo 3

Vamos supor que temos a seguinte lista ordenada:
Lista = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
Queremos procurar o número 10 usando a busca binária. Veja como fazemos isso passo a passo:
  1. Primeiro passo: Olhamos o elemento do meio da lista. Como temos 10 elementos, o meio fica na posição 5 (começando do 1), que é o número 10.
    Meio = 1 + 102 = 5.5 approx 5 (arredondamos para baixo)
    E<=mento central = 10
  2. Comparação: O elemento central é igual a 10, que é o que estamos procurando.

Passo 4

Como o elemento central já era o 10, encontramos o número na primeira tentativa! Isso mostra que, mesmo no melhor caso, a busca binária pode ser muito eficiente. Mas o mais importante aqui é entender por que isso funcionou tão bem: a lista estava ordenada.

Resposta

Aplicando a busca binária na lista ordenada 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, encontramos o número 10 imediatamente ao comparar com o elemento central. Isso indica que, para usar a busca binária, a lista precisa estar ordenada previamente.

Exercícios relacionados