- Valor procurado
- Ainda possíveis
- Comparados
- Excluídos
- Encontrados
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
- 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.
- 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.
- 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