Sondagens
Ainda possíveis
A pesquisa binária precisaria de

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

Mais sobre a pesquisa por interpolação

Pesquisa por interpolação

A pesquisa por interpolação procura um valor numa lista ordenada como quem abre uma lista telefónica: para um nome começado por T, abre perto do fim, não no meio. Estima a posição do valor procurado a partir dos valores das duas pontas da parte que resta. Escolha o valor e a distribuição, avance pelas sondagens passo a passo e veja quando a estimativa bate a pesquisa binária e quando não. 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 mostra onde ainda pode estar. A pesquisa por interpolação precisa de uma lista ordenada, por isso uma lista desordenada é ordenada primeiro. Escolha o valor, como os valores se distribuem, 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, como os valores se distribuem e quantas barras. Ou escreva os seus próprios números: a pesquisa por interpolação 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. Mude «Distribuição» entre «Uniforme», «Intervalos aleatórios» e «Enviesada», e compare «Sondagens» com «A pesquisa binária precisaria de».

Como funciona a pesquisa por interpolação

Olhe para o primeiro e o último valor da parte da lista ordenada que ainda pode conter o valor procurado. Se o valor procurado estiver, por exemplo, a 40% do caminho entre o primeiro valor e o último, sonde a posição a 40% da lista. Se o valor nessa posição for o procurado, terminou. Se for menor, só restam as posições seguintes; se for maior, só as anteriores. Volte a estimar no que resta. Se o valor procurado for menor do que o primeiro valor ou maior do que o último, não está lá.

Quando a estimativa funciona

Se os valores estiverem distribuídos uniformemente, como 10, 20, 30 e assim por diante, a primeira estimativa cai no valor procurado ou muito perto, e a pesquisa precisa em média de cerca de log₂(log₂ n) sondagens: cerca de 5 para mil milhões de valores, contra 30 da pesquisa binária. Se os valores se amontoarem, como 1, 2, 3, 4, 1000, as estimativas continuam a cair no sítio errado e cada sondagem pode excluir apenas um valor, por isso o pior caso são n sondagens. A pesquisa binária nunca precisa de mais de cerca de log₂ n.

Perguntas frequentes

Como funciona a pesquisa por interpolação?

Numa lista ordenada, estima onde o valor procurado deveria estar a partir do primeiro e do último valor da parte que resta, sonda essa posição e fica só com a parte do lado certo. É como a pesquisa binária, mas com uma estimativa mais inteligente do que o meio.

A pesquisa por interpolação é mais rápida do que a pesquisa binária?

Com valores distribuídos uniformemente, sim: em média cerca de log₂(log₂ n) sondagens em vez de cerca de log₂ n. Com valores distribuídos de forma irregular pode ser muito mais lenta, até n sondagens, enquanto a pesquisa binária nunca precisa de mais de cerca de log₂ n.

Porque pode ser lenta?

Porque a estimativa assume que os valores crescem de forma uniforme. Se a maioria dos valores for pequena e alguns forem enormes, a estimativa para um valor procurado pequeno cai repetidamente perto do início e só exclui um ou dois valores de cada vez.

Onde se usa a pesquisa por interpolação?

Onde as chaves estão distribuídas de forma quase uniforme e as sondagens são caras, como ao procurar registos em disco por ID numérico ou hash. Muitos sistemas combinam-na com a pesquisa binária para manter um bom pior caso.

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