Esse algoritmo ainda pode ser considerado um algoritmo de Pesquisa Binária?

14

Enquanto fazia o segundo código kata (que solicita a implementação de um algoritmo de pesquisa binária cinco vezes, cada vez com um método diferente), criei uma solução ligeiramente diferente que funciona da seguinte maneira:

Se eu tiver uma matriz classificada com o comprimento 100 e vejo que o campo inicial contém o número 200 e o campo final contém o número 400, eu, como um matemático que estuda humano, provavelmente começaria a pesquisar no campo 35 se estivesse pesquisando o número 270, e não o campo 50 como em um algoritmo de pesquisa binária normal.

Então, se o número no campo 35 da matriz for 270, 35 é o índice que eu estava procurando.

Se esse não for o caso, posso comparar o número obtido (digamos 280) e repetir a operação na parte inferior da matriz (então, tenho 35 campos com o campo inicial contendo 200 e o final com 280) se o o número que encontrei é maior do que o que estou procurando, ou a parte superior da matriz (digamos que tenho 260: agora tenho 65 índices, o primeiro contendo 260 e o final contendo 400. Orientativamente, eu iria índice 4 dessa sub-matriz, que é o índice 39 de toda a matriz) se o número que eu obtiver for menor que o número que estou procurando.

A questão é: esse algoritmo pode ser considerado um algoritmo de pesquisa binária? Caso contrário, ele tem seu próprio nome?

algorithms terminology search-algorithms binary-search user6245072
fonte
2
Quer se trate de pesquisa binária ou não, parece ser apenas uma questão de opinião. Essencialmente, a única resposta que você pode dar é "Sim, é perto o suficiente da pesquisa binária para chamá-la de pesquisa binária" ou "Não, não é". Argumento segue.
David Richerby

Respostas:

23

Eu não chamaria isso de uma pesquisa binária.

É claramente semelhante à pesquisa binária e é natural vê-la como um refinamento da pesquisa binária. No entanto, possui características de complexidade de algoritmo significativamente diferentes, a Pesquisa de Interpolação espera o tempo de execução de O (log (log (n)) assumindo que os dados são distribuídos uniformemente, no entanto, compensa isso tendo O (n) pior caso de tempo de execução.

Prefiro dizer "O pior caso de tempo de execução da pesquisa binária é O (log (n))" em vez de "Dependendo da escolha dos elementos delimitadores, o pior caso de tempo de execução da pesquisa binária é O (log (n))". Isso significa que não consigo classificar a pesquisa de interpolação como um algoritmo de pesquisa binária.

Taemyr
fonte
Presumivelmente, se você interromper a pesquisa de interpolação quando estiver indo mal, poderá reter O (log n) no pior caso e O (log log n) em dados suficientemente lineares. Meu palpite é que algo como "se eu não encontrei o alvo após as tentativas de log n, em seguida, alterne para a pesquisa binária" funcionará, mas estou com preguiça de provar isso. Obviamente, haverá uma classe de entradas matadoras nas quais isso leva basicamente o dobro do tempo que uma pesquisa binária.
Steve Jessop
Essa ideia do assassino é interessante. E se, em vez de permitir que entradas matadoras afetassem negativamente a pesquisa (ou seja, dividindo perto do final de uma matriz), limitamos / aparamos o "intervalo divisível" para o 2º terço da matriz ou similar. Isso teria o pior caso log3 (n), mas ainda desfrutaria de um melhor caso de log (log).
Andrew Gallasch
1
@SteveJessop Lembre-se de que a complexidade assintótica não é a imagem completa. O (log n) é muito rápido. Além disso, a pesquisa binária faz muito pouco trabalho em cada loop. Portanto, o problema da pesquisa de interpolação já é que você precisa de muito tempo para compensar o fato de trabalhar mais em cada loop. Sua sugestão acrescenta mais trabalho a isso. Se não consegui aceitar O (n) para dados que não eram uniformes, suspeito que a melhor solução é procurar uma pesquisa binária pura, em vez de uma abordagem híbrida.
21416 Taemyr
@ SteveJessop: Não há necessidade de alternar algoritmos; isso pode ser feito em paralelo. Dado um intervalo R, você pode determinar o ponto P1 como o ponto médio usual para pesquisa binária e P2 usando interpolação. Agora você tem três subintervalos, nenhum dos quais pode ser maior que a metade do intervalo original. Verifique o valor-alvo em relação a P1 e P2, e você sabe em qual das três subfaixas deve recorrer.
MSalters
17

O(registro⁡registro⁡n)

Tom van der Zanden
fonte
Legal. Agora a questão é se eu posso usá-lo para o código kata, mas é o meu problema lol. Estou achando isso mais complicado do que a pesquisa binária, então por que não?
user6245072
Descobri isso uma vez ao escrever um código para indexar um arquivo de log há alguns anos atrás. Também descobri que, para meus dados, as etapas alternadas entre interpolação e fatia binária eram melhores do que qualquer opção por si só. Não tenho certeza se isso tem um nome ou é um efeito conhecido.
Neil Slater
@ NeilSlater hedged busca interpolação talvez?
Steve Cox
@SteveCox: Acabei de pesquisar esse termo e não encontrei nada. Decidiu fazer isso como uma nova pergunta: cs.stackexchange.com/questions/59750/…
Neil Slater
-1

Penso que a terminologia correta seria uma pesquisa ponderada dicotomial.

Você procura em uma matriz plana com a subsequente busca ponderada com base na suposta distribuição plana dos números contidos nela.

Isso corresponde a como uma pessoa pesquisaria uma palavra em um dicionário. Mas pode ser muito ineficiente se a distribuição dos dados for irregular.

Ludovic Zenohate Lagouardette
fonte