A pesquisa linear e a busca binária são algoritmos comuns usados para encontrar elementos dentro de uma lista. Compreender o número esperado de comparações que cada algoritmo faz pode ajudar na escolha do método mais eficiente para situações específicas. Este artigo compara as comparações esperadas em métodos de pesquisa linear versus binária.

Pesquisa Linear

A pesquisa linear verifica cada elemento da lista sequencialmente até que encontre o alvo ou chegue ao fim. O número esperado de comparações depende da presença do alvo e da sua posição na lista.

Se a lista contiver elementos n e o alvo for igualmente provável de estar em qualquer posição, o número de comparações esperado é:

Comparações esperadas = (n + 1) / 2

Isto porque, em média, a busca vai encontrar o alvo a meio caminho da lista.

Pesquisa Bíntica

A pesquisa binária funciona em listas ordenadas dividindo repetidamente o intervalo de busca ao meio. A sua eficiência depende do tamanho da lista e da posição do alvo.

No melhor dos casos, o alvo está no meio, requerendo apenas uma comparação. No pior dos casos, ele leva aproximadamente ]log2[ n] comparações.

Assumindo que o objectivo é igualmente provável que se encontre em qualquer posição, o número de comparações esperado é aproximadamente:

Comparações esperadas □ log2 n

Resumo da Comparação

  • A pesquisa linear tem uma contagem de comparação esperada de (n + 1) / 2.
  • A pesquisa binária tem uma contagem de comparação esperada de aproximadamente log2 n.
  • A busca binária geralmente requer menos comparações para grandes listas.
  • A pesquisa linear pode ser preferível para listas pequenas ou não.