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.
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