Existe algum estudo ou teoria por trás da combinação de pesquisa binária e pesquisa de interpolação?

Acabei de ler Esse algoritmo ainda pode ser considerado um algoritmo de Pesquisa Binária? e lembrei que, alguns anos atrás, escrevi um indexador / pesquisei arquivos de log para encontrar entradas de log em grandes arquivos de texto sem formatação por janela de data / hora.

Enquanto fazia isso, decidi tentar a pesquisa de interpolação (não sabia como era chamado, meio que me deparei com a ideia). Então, por algum motivo, continuei com a ideia de alternar etapas de interpolação com etapas binárias de divisão: na etapa 0, eu interpolava para decidir o ponto de teste, depois a etapa 1 usava o ponto médio exato, etc.

Em seguida, comparei o sistema usando pesquisa de interpolação pura, pesquisa binária pura e minha tentativa de combinação. A abordagem alternativa foi uma vencedora clara, tanto no tempo quanto no número de testes necessários antes de encontrar um conjunto de horários escolhidos aleatoriamente.

Inspirado na pergunta vinculada, fiz uma pesquisa rápida por "pesquisa de interpolação alternada e pesquisa binária" e não encontrei nada. Eu também tentei "pesquisa de interpolação com cobertura", conforme sugerido no meu comentário em uma das respostas.

Eu me deparei com uma coisa conhecida? Existe alguma justificativa teórica para ser mais rápido para certos tipos de dados? Os arquivos de log eram geralmente grandes para a época (por exemplo, 1-2 GB de texto com talvez 10 milhões de linhas para pesquisar), e a distribuição de datas / horas neles era complexa, com fortes explosões de atividade, horários de pico em geral e horários de silêncio. Meus testes de referência foram amostrados a partir de uma distribuição uniforme dos tempos-alvo a serem encontrados.

Eu me deparei com uma coisa conhecida?

Existem vários métodos, baseados em uma combinação de pesquisa de interpolação e pesquisa binária, com um tempo médio de acesso ao caso (distribuição uniforme) e tempo de pior caso (valores distribuídos de maneira desigual) :$O(log\ log\ n)$$O(log\ n)$

• A pesquisa introspectiva é o seu método (iterando entre uma pesquisa de interpolação e uma pesquisa binária). Não tenho mais detalhes.

• Pesquisa binária de interpolação (IBS) por N. Santoro, JB Sidney (1985).

  A idéia geral é que a pesquisa de interpolação é útil apenas quando a matriz pesquisada é maior que um determinado limite. Quando o segmento de pesquisa considerado é menor que um limite definido pelo usuário, a pesquisa binária é aplicada incondicionalmente. Vice-versa, acima desse limite, uma etapa de pesquisa de interpolação é aplicada, seguida por uma etapa de pesquisa binária.

  Isso tem muitos pontos em comum com sua abordagem.

• Pesquisa adaptativa (AS) de Biagio Bonasera, Emilio Ferrara, Giacomo Fiumara, Francesco Pagano, Alessandro Provetti

  Usando as palavras dos autores:

  A [Pesquisa binária de interpolação] criou uma solução semelhante que combina (mas não combina) a interpolação e a pesquisa binária. Embora a complexidade assintótica seja a mesma, existem algumas diferenças marcantes.

  [CORTAR]

  Portanto, é possível mostrar que, para qualquer entrada, o AS não precisará de operações mais elementares que o IBS.

  O algoritmo pode gastar até o dobro de operações que a pesquisa de interpolação "simples" para descobrir cuidadosamente a melhor metade do segmento de pesquisa, o que, por sua vez, significa que menos iterações serão necessárias para concluir (mas você tem uma sobrecarga ainda maior) .

A intercalação de dois algoritmos para obter o melhor dos dois mundos é uma técnica conhecida, embora geralmente seja declarada como executá-los em "paralelo" e retornar uma resposta assim que terminar.

Embora teoricamente mais rápida, a pesquisa de interpolação tem duas desvantagens em comparação com a pesquisa binária:

• Tem um desempenho terrível (linear) no pior dos casos

• A sobrecarga da computação no ponto médio é bastante grande; uma iteração de pesquisa binária é centenas de vezes mais rápida que uma interpolação

Eu esperaria que uma abordagem em que você faça a pesquisa de interpolação enquanto o intervalo é grande e alterne para a pesquisa binária quando o intervalo se tornar pequeno é a mais eficiente. Seria bom se você pudesse tentar esse experimento.

$\log n$$\log \log n$$\log n$$\log \log n$

Eu acho que seus resultados podem ser explicados por dois fenômenos:

• A combinação com a pesquisa binária permite evitar o pior comportamento

• O efeito positivo da mudança para a pesquisa binária em um pequeno conjunto de dados