Pesquisa de interpolação vs Pesquisa binária

Quando devo usar a pesquisa de interpolação em vez da pesquisa binária?

Por exemplo, eu tenho um conjunto de dados classificado, em quais situações eu usaria a pesquisa binária para encontrar um item nesse conjunto de dados ou em qual situação devo usar a pesquisa de interpolação?

Quais propriedades do conjunto de dados seriam o fator determinante?

Obviamente, para fazer uma pesquisa de interpolação, você precisa de algum tipo de chave para a qual sejam conhecidas mais do que pedidos - você deve poder fazer cálculos nas teclas para estimar uma distância provável, não apenas comparar chaves para determinar qual é maior ou menor.

No que diz respeito às propriedades do conjunto de dados, trata-se principalmente de uma propriedade: uma probabilidade de que as chaves sejam razoavelmente uniformes (ou pelo menos previsíveis) distribuídas por toda a gama de possibilidades. Sem isso, uma pesquisa de interpolação pode realmente ser mais lenta que uma pesquisa binária.

Por exemplo, considere um conjunto de dados com cadeias de letras minúsculas como chaves. Vamos supor que você tenha uma chave que comece com "x". Uma pesquisa de interpolação indicará claramente que você deve começar a pesquisar muito perto do final do conjunto. Se, no entanto, a maioria de suas chaves começar com 'z' e quase nenhuma com algo de 'a' a 'y', a que você está procurando pode estar muito perto do início do conjunto. Pode / pode levar um número considerável de iterações antes que a pesquisa chegue perto do início em que a sequência iniciada por 'w' reside. Cada iteração removeria apenas ~ 10% do conjunto de dados da consideração; portanto, levaria várias iterações antes de chegar perto do início, onde as chaves que começam com 'w'

Por outro lado, uma pesquisa binária começaria no meio, alcançaria a marca de um quarto na segunda iteração, a oitava marca na terceira e assim por diante. Seu desempenho não seria afetado pela distorção nas teclas. Cada iteração removeria metade do conjunto de dados da consideração, como se as chaves fossem distribuídas igualmente.

Apresso-me a acrescentar, no entanto, que realmente é necessária uma distribuição bastante distorcida para tornar uma pesquisa de interpolação visivelmente pior do que uma pesquisa binária. Pode, por exemplo, ter um desempenho muito bom, mesmo na presença de uma quantidade razoável de armazenamento em cluster localizado.

Também devo mencionar que uma pesquisa de interpolação não precisa necessariamente usar interpolação linear. Por exemplo, se suas chaves seguem uma distribuição não linear (por exemplo, uma curva em sino), torna-se bastante fácil levar isso em consideração na função de interpolação para obter resultados um pouco diferentes de uma distribuição uniforme.

Eu provavelmente pensaria que a pergunta é com que facilidade você pode criar uma função de interpolação que realmente se sai melhor do que a pesquisa binária.

Da Wikipedia na pesquisa de interpolação:

Usando a notação big-O, o desempenho do algoritmo de interpolação em um conjunto de dados de tamanho N é O (N); no entanto, sob a suposição de uma distribuição uniforme dos dados na escala linear usada para interpolação, o desempenho pode ser mostrado como O (log log N).

O desempenho prático da pesquisa de interpolação depende se o número reduzido de sondas é compensado pelos cálculos mais complicados necessários para cada sonda. Pode ser útil para localizar um registro em um grande arquivo classificado no disco, onde cada sonda envolve uma busca no disco e é muito mais lenta que a aritmética da interpolação.

Estruturas de índice como árvores B também reduzem o número de acessos ao disco e são mais frequentemente usadas para indexar dados no disco, em parte porque podem indexar muitos tipos de dados e podem ser atualizados online. Ainda assim, a pesquisa de interpolação pode ser útil quando alguém é forçado a pesquisar determinados conjuntos de dados no disco classificados, mas não indexados.

Pesquisa binária e pesquisa de interpolação são consideradas métodos de pesquisa linear.

Ambos esperam que a lista que está sendo pesquisada seja classificada na coluna referida como chave . Isto é muito importante.

A pesquisa binária funciona para cadeias ou números, desde que eles sejam armazenados em ordem classificada. A idéia principal por trás da pesquisa binária é que ela se baseia no exame do elemento do meio. A pesquisa de interpolação é uma variante. Em vez de usar o elemento do meio exato, ele adivinha onde está o próximo elemento a ser comparado com o valor passado. Consulte a referência fornecida pela resposta JB King ou a abaixo nesta resposta para obter detalhes sobre como o algoritmo de pesquisa de interpolação calcula o próximo valor da chave.

"A pesquisa de interpolação funciona apenas em elementos numéricos organizados em ordem de matrizes ordenadas com distribuição uniforme (ou seja, o intervalo entre qualquer elemento e sucessivos é aproximadamente constante" (citação da referência abaixo da P 737, também é incluída uma comparação de desempenho entre diferentes métodos de pesquisa linear) )

Google Livros - Estruturas clássicas de dados 2º ed.