Busca sequencial x busca binária – contando comparações

O que mostra

A busca sequencial verifica os elementos um a um desde o início, então no pior caso precisa de tantas comparações quanto o número de elementos. A busca binária compara o valor procurado com o elemento do meio de um vetor ordenado e descarta a metade que não pode contê-lo, por isso precisa de no máximo cerca de log₂n + 1 comparações: apenas cinco para dezesseis elementos. Contar as comparações dos dois algoritmos no mesmo vetor mostra por que a binária vence em listas longas e por que ela depende totalmente de os dados estarem ordenados.

Como usar

Coloque Algoritmo em Os dois (comparar), escolha o Número de elementos e clique em Passo para acompanhar cada comparação: a célula destacada, os marcadores low, mid e high e a parte do vetor descartada. Clique em uma célula para mudar o valor procurado ou use Reproduzir para uma execução completa. Teste um valor perto do início do vetor e depois desmarque Vetor em ordem crescente para ver por que a busca binária deixa de funcionar.

Parâmetros que você pode mudar

• Número de elementos 5–20
• Valor procurado (0 = sortear do vetor) 0–99
• Algoritmo Os dois (comparar), Busca sequencial, Busca binária
• Vetor em ordem crescente
• Velocidade de execução 1–5 passos/s

Perguntas para explorar

1. Qual é o maior número de comparações de que a busca binária precisa para achar um valor num vetor de 16 elementos?
2. Para quais valores procurados a busca sequencial precisa de menos comparações que a binária?
3. Por que a busca binária não pode ser usada quando o vetor não está ordenado?