Suponha que um elemento é conhecido por estar entre os quatro primeiros elementos de uma lista com 32 elementos. Uma busca linear ou uma busca binária localizaria este elemento mais rapidamente?

Passo 1

O enunciado diz que temos uma lista com 32 elementos e sabemos que o elemento buscado está entre os quatro primeiros. Queremos comparar o número de comparações necessárias em uma busca linear e em uma busca binária para decidir qual localizaria o elemento mais rapidamente. Vamos usar a contagem de comparações no pior caso e a média quando o elemento está uniformemente distribuído nas posições de 1 a 4.

Passo 2

Na busca linear, examinamos um a um os elementos a partir do primeiro até encontrarmos o alvo.
No pior caso, o alvo está na 4ª posição, então fazemos 4 comparações.
Se supusermos que o alvo está igualmente provável em cada uma das quatro posições, o número médio de comparações é
\frac{1+2+3+4}{4} = \frac{10}{4} = 2{,}5.

Passo 3

Na busca binária em uma lista de 32 elementos, precisamos de no máximo
\lceil \log_{2}(32)\rceil = 5
comparações para decidir e encontrar o elemento. Mas, restringindo ao fato de que o alvo está entre as posições 1 e 4, podemos contar quantas comparações ocorrem em cada posição:
  1. Se o alvo está na posição 1, as comparações vão aos pivôs nos índices 16, 8, 4, 2 e finalmente 1, totalizando 5 comparações.
  2. Se está na posição 2, os pivôs serão 16, 8, 4 e 2, totalizando 4 comparações.
  3. Se está na posição 3, vamos em 16, 8, 4, 2 e depois 3, totalizando 5 comparações.
  4. Se está na posição 4, vamos em 16, 8 e 4, totalizando 3 comparações.
Assim, o número médio de comparações é
\frac{5 + 4 + 5 + 3}{4} = \frac{17}{4} = 4{,}25.

Passo 4

Comparando os resultados:
— Busca linear: no pior caso 4 comparações e média de 2{,}5.
— Busca binária: no pior caso 5 comparações e média de 4{,}25.
Como 2{,}5 é muito menor que 4{,}25 e também 4 < 5, a busca linear localizará o elemento mais rapidamente quando sabemos que ele está entre os quatro primeiros.

Resposta

Busca linear.

Exercícios de Livros Relacionados