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 é
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 é
Passo 3
Na busca binária em uma lista de 32 elementos, precisamos de no máximo
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:
- 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.
- Se está na posição 2, os pivôs serão 16, 8, 4 e 2, totalizando 4 comparações.
- Se está na posição 3, vamos em 16, 8, 4, 2 e depois 3, totalizando 5 comparações.
- 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 é
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.
— 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.