Pesquisa por interpolação

Quando procura «Taylor» numa lista telefónica, não a abre no meio: abre-a perto do fim, porque o T vem tarde no alfabeto. A pesquisa por interpolação faz o mesmo com números. Adivinha onde o valor procurado deveria estar pelo seu tamanho e, com dados distribuídos uniformemente, essa estimativa é notavelmente boa.

Uma fila ordenada de barras com uma linha da primeira à última barra, e a sondagem colocada onde a altura do valor procurado encontra essa linha
Uma fila ordenada de barras com uma linha da primeira à última barra, e a sondagem colocada onde a altura do valor procurado encontra essa linha

A ideia

A pesquisa binária sonda sempre o meio, seja o que for que procure. A pesquisa por interpolação usa os valores. Se a parte da lista que resta vai de 10 a 100 e o valor procurado é 70, este está a dois terços do caminho entre o primeiro valor e o último, por isso sonda a dois terços da lista. Em fórmula, a sondagem fica em lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). Após a sondagem, fica com a parte do lado certo, exatamente como a pesquisa binária, e volta a estimar.

Dois exemplos

Em 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, procurar 70 sonda logo a posição 7: encontrado em 1 sondagem, onde a pesquisa binária precisa de 4. Agora pegue em 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 e procure 9. Por causa do 999, cada estimativa cai perto do início: a pesquisa sonda 1, 2, 3 e assim por diante, uma posição de cada vez, e precisa de 9 sondagens onde a pesquisa binária precisa de 3.

Quão rápida é

Quando os valores estão distribuídos uniformemente, ou são tirados ao acaso de uma distribuição uniforme, cada sondagem reduz a parte que resta de cerca de n para cerca de √n. Isso dá em média cerca de log₂(log₂ n) sondagens: cerca de 5 mesmo para mil milhões de valores, contra 30 da pesquisa binária. Quando os valores estão distribuídos de forma muito irregular, uma sondagem pode excluir apenas um valor, e o pior caso são n sondagens, tão mau como a pesquisa linear. Cada sondagem custa também uma divisão, por isso na prática compensa sobretudo quando as sondagens são caras, como leituras do disco.

História e variantes

W. W. Peterson descreveu a pesquisa por interpolação em 1957, para encontrar registos em memória de acesso aleatório. A sua média de log log n para chaves distribuídas uniformemente foi demonstrada em 1978 por Perl, Itai e Avni. As versões práticas protegem-se de dados desfavoráveis intercalando passos binários, por exemplo a pesquisa interpolação-sequencial ou interpolação-binária, para que o pior caso fique perto de log n.

Experimente

Abra a aplicação, escolha um valor em «Procurar» e prima «Avançar». Cada sondagem diz em que ponto o valor procurado está entre os dois valores das pontas e para que posição isso aponta. Mude «Distribuição» para «Uniforme» e a maioria das pesquisas termina numa sondagem; mude para «Enviesada» e as sondagens arrastam-se pelo início da lista. O último contador mostra de quantos passos a pesquisa binária precisaria para o mesmo valor.

Perguntas frequentes

Qual é a complexidade temporal da pesquisa por interpolação?

O(log log n) em média para valores distribuídos uniformemente, e O(n) no pior caso. Precisa de O(1) de memória extra e de uma lista ordenada.

Qual é a diferença entre a pesquisa por interpolação e a pesquisa binária?

A pesquisa binária sonda sempre o meio do que resta. A pesquisa por interpolação sonda onde o valor procurado deveria estar, a julgar pelos valores das duas pontas. Isso é muito melhor com valores distribuídos uniformemente e pode ser muito pior com valores enviesados.

Que dados são adequados à pesquisa por interpolação?

Chaves numéricas ordenadas e distribuídas de forma bastante uniforme: IDs sequenciais com poucas falhas, marcas temporais de eventos regulares ou chaves com hash. Adequa-se a dados em que uma sondagem é cara e um pouco de aritmética custa pouco.

Porque é que a aplicação oferece distribuições diferentes?

Porque a distribuição decide quão boas são as estimativas. Com valores uniformes, a pesquisa por interpolação parece quase mágica, e os valores enviesados mostram a sua fraqueza. Compará-los com a contagem da pesquisa binária é a forma mais clara de ver quando usar cada uma.

Pronto para experimentar?

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

Experimente a pesquisa por interpolação