Comparações
Ainda possíveis
A pesquisa binária precisaria de

  • Valor procurado
  • Ainda possíveis
  • Comparados
  • Excluídos
  • Encontrados

Mais sobre a pesquisa exponencial

Pesquisa exponencial

A pesquisa exponencial encontra um valor numa lista ordenada em duas fases. Primeiro verifica as posições 1, 2, 4, 8, 16 e assim por diante, duplicando de cada vez, até o valor nessa posição não ser menor do que o valor procurado. Depois aplica a pesquisa binária ao intervalo entre as duas últimas posições. Escolha o valor a procurar e veja porque é que os valores perto do início são encontrados com poucas comparações. Prima Reproduzir para ver a pesquisa, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. A linha tracejada marca o valor que procura, e a parte sombreada é onde ainda pode estar. A pesquisa exponencial precisa de uma lista ordenada, por isso uma lista desordenada é ordenada primeiro. Escolha o valor, quantas barras, ou escreva os seus próprios números. Com o quadro selecionado, as setas avançam e recuam, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.

Como funciona

  1. Escolha o valor a procurar e quantas barras. Ou escreva os seus próprios números: a pesquisa exponencial ordena-os primeiro.
  2. Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto da pesquisa.
  3. Procure um valor perto do início e outro perto do fim, e compare a contagem com «A pesquisa binária precisaria de».

Como funciona a pesquisa exponencial

Verifique o valor na posição 1. Se for menor do que o valor procurado, verifique a posição 2, depois a 4, 8, 16, duplicando de cada vez. Assim que um valor não for menor, pare: o valor procurado só pode estar depois da posição verificada antes e antes desta. Aplique a pesquisa binária a esse intervalo. Se a duplicação ultrapassar o fim da lista, aplique a pesquisa binária desde a última posição verificada até ao fim.

Rápida no início, sem precisar do comprimento

Para chegar a um valor na posição i, a duplicação precisa de cerca de log₂ i verificações, e o intervalo encontrado tem menos de i valores, por isso a pesquisa binária precisa de cerca de mais log₂ i. No total são cerca de 2 log₂ i, o que depende de onde está o valor procurado e não do comprimento da lista. Os valores perto do início são encontrados mais depressa do que com a pesquisa binária simples; os valores perto do fim custam até cerca do dobro. Como nunca precisa do comprimento da lista, também funciona com listas demasiado longas para medir ou sem fim conhecido.

Perguntas frequentes

Como funciona a pesquisa exponencial?

Numa lista ordenada, verifica as posições 1, 2, 4, 8 e assim por diante até o valor nessa posição não ser menor do que o valor procurado. Então o valor procurado só pode estar entre as duas últimas posições verificadas, e uma pesquisa binária nesse intervalo encontra-o.

A pesquisa exponencial é mais rápida do que a pesquisa binária?

Quando o valor procurado está perto do início da lista, sim: precisa de cerca de 2 log₂ i comparações para um valor na posição i, seja qual for o comprimento da lista. Quando está perto do fim, a pesquisa binária simples é mais rápida, até cerca do dobro.

Para que serve?

Para pesquisar listas de comprimento desconhecido ou ilimitado, como um fluxo ou uma sequência infinita, e para fundir sequências ordenadas, onde a correspondência seguinte costuma estar perto. O modo galope do Timsort usa a mesma ideia de duplicar.

Porque se chama exponencial?

Porque as posições que verifica crescem exponencialmente: 1, 2, 4, 8, 16, cada uma o dobro da anterior. Também se chama pesquisa por duplicação ou pesquisa galopante.

Os meus números são enviados para algum lado?

Não. A pesquisa corre no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor