Pesquisa por saltos
A pesquisa por saltos é a forma como procura uma página num livro sem índice: avança um bloco de páginas de cada vez, olhando para os números das páginas, e quando passa do ponto, folheia para trás o último bloco. Numa lista ordenada precisa de muito menos comparações do que verificar cada valor.
A ideia
Numa lista ordenada, o último valor de um bloco diz-lhe se o alvo pode sequer estar nesse bloco: se for menor do que o alvo, todos os valores do bloco também são. Por isso, não é preciso olhar lá para dentro. Verifique à vez o último valor de cada bloco, saltando blocos inteiros, até um não ser menor do que o alvo. Então o alvo só pode estar nesse bloco: percorra-o desde o início.
Um exemplo
Procure 23 em 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, com blocos de 3. O primeiro bloco termina em 8, que é menor, por isso salta-se. O segundo termina em 23, que não é menor, por isso 23 só pode estar em 12, 16, 23. Percorrê-lo dá 12, 16 e depois 23: encontrado após 5 comparações, quando a pesquisa linear precisa de 6 e a binária de 3. Ao procurar 40, os finais de bloco 8, 23 e 72 levam ao bloco 38, 56, 72; 38 é menor e 56 já é maior, por isso 40 não está lá: outra vez 5 comparações.
Porquê √n
Com blocos de m valores, encontrar o bloco certo custa no máximo cerca de n/m comparações e percorrê-lo no máximo m. Poucos saltos longos tornam o percurso longo; muitos saltos curtos tornam os saltos longos. A soma n/m + m é mínima quando as duas partes são iguais, com m = √n, em que vale cerca de 2√n. Para 40 valores, isso significa blocos de 6 e no máximo 13 comparações; para um milhão de valores, blocos de 1000 e cerca de 2000 comparações.
Onde se encaixa
A pesquisa binária precisa de menos comparações, cerca de log₂ n. Mas salta para trás e para a frente por toda a lista, enquanto a pesquisa por saltos só avança e recua uma vez, até ao início de um bloco. Isso tornava-a atrativa para dados em fita ou numa estrutura ligada, onde recuar é lento. Ben Shneiderman descreveu-a como «jump searching» em 1978. A mesma ideia de dividir em blocos de √n, muitas vezes chamada decomposição em raiz quadrada, aparece em muitos outros algoritmos.
Explore
Abra a aplicação, escolha um valor em Procurar e prima Avançar. Cada salto destaca o último valor de um bloco; os blocos saltados esbatem-se, e o bloco que pode conter o alvo fica sombreado enquanto é percorrido. Com 40 barras, mude Tamanho do salto de √n para 2 ou 8 e veja o equilíbrio entre saltos e percurso mudar.
Perguntas frequentes
Qual é a complexidade temporal da pesquisa por saltos?
O(√n) com blocos de √n valores: no máximo cerca de 2√n comparações. Precisa de memória adicional O(1) e de uma lista ordenada.
Qual é a diferença entre a pesquisa por saltos e a pesquisa binária?
A pesquisa binária reduz para metade a parte restante de cada vez e precisa de cerca de log₂ n comparações, mas anda para trás e para a frente. A pesquisa por saltos avança em passos fixos e percorre um bloco, precisa de cerca de 2√n comparações e só recua uma vez.
Pode usar-se a pesquisa binária no último bloco?
Sim. Pesquisar o bloco com pesquisa binária reduz o percurso de m comparações para cerca de log₂ m. Os saltos continuam a custar n/m, por isso passam a compensar blocos maiores.
A pesquisa por saltos precisa de uma lista ordenada?
Sim. Saltar um bloco só é seguro porque, se o último valor for menor, todos os valores do bloco também são. A aplicação ordena primeiro uma lista desordenada.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Experimentar a pesquisa por saltos