Comparações
Tamanho do salto
A pesquisa linear precisaria de

  • Valor procurado
  • Bloco atual
  • Comparados
  • Excluídos
  • Encontrados

Mais sobre a pesquisa por saltos

Pesquisa por saltos

A pesquisa por saltos fica entre a pesquisa linear e a binária. Avança por uma lista ordenada em saltos de m posições, verificando apenas o último valor de cada bloco, até chegar a um bloco cujo último valor não é menor do que o alvo. Depois percorre esse bloco desde o início. Escolha o valor e o tamanho do salto, e veja de quantas comparações precisam os saltos e o percurso. Prima Reproduzir para ver a pesquisa, ou Avançar e Recuar para ir uma comparação de cada vez. Arraste a barra de passos para saltar para qualquer ponto. A linha tracejada marca o valor que procura, e a parte sombreada é o bloco atual. A pesquisa por saltos precisa de uma lista ordenada, por isso uma lista desordenada é ordenada primeiro. Escolha o valor, o tamanho do salto, quantas barras, ou escreva os seus próprios números. Com o quadro selecionado, as setas avançam e recuam, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.

Como funciona

  1. Escolha o valor a procurar, o tamanho do salto e quantas barras. Ou escreva os seus próprios números: a pesquisa por saltos ordena-os primeiro.
  2. Prima Reproduzir, ou use Avançar e Recuar para ir uma comparação de cada vez. Arraste a barra de passos para saltar para qualquer ponto da pesquisa.
  3. Com 40 barras, experimente um tamanho de salto de 2 e de 8, e compare o número de comparações com o de √n.

Como funciona a pesquisa por saltos

Divida a lista ordenada em blocos de m valores. Olhe para o último valor do primeiro bloco. Se for menor do que o alvo, o alvo não pode estar em nenhum ponto desse bloco, por isso salte para o fim do bloco seguinte e olhe de novo. Assim que o último valor de um bloco não for menor, o alvo só pode estar nesse bloco: volte ao seu início e verifique os seus valores um a um até encontrar o alvo ou passar por ele.

Escolher o tamanho do salto

Com n valores, os saltos custam até n/m comparações e o percurso até m. Saltos pequenos tornam o percurso curto, mas os saltos numerosos; saltos grandes fazem o contrário. O total n/m + m é mínimo quando m = √n, o que dá cerca de 2√n comparações: no máximo 13 para 40 valores, contra 40 da pesquisa linear e 6 da binária. A pesquisa por saltos nunca recua mais do que um bloco, o que ajuda quando andar para trás nos dados é lento.

Perguntas frequentes

Como funciona a pesquisa por saltos?

Numa lista ordenada, salta em frente de m em m posições e verifica o último valor de cada bloco. Quando esse valor já não é menor do que o alvo, o alvo só pode estar nesse bloco, que depois percorre desde o início.

Qual é o melhor tamanho de salto?

√n, arredondado. Os saltos custam até n/m comparações e o percurso até m, e a soma é mínima quando os dois são iguais, com m = √n. Isso dá cerca de 2√n comparações no pior caso.

A pesquisa por saltos é mais rápida do que a pesquisa binária?

Não, a pesquisa binária precisa de menos comparações: cerca de log₂ n contra cerca de 2√n. Ainda assim, a pesquisa por saltos pode ganhar quando recuar nos dados é caro, porque só recua uma vez, até ao início de um bloco.

Que correspondência encontra quando há valores repetidos?

A primeira. Cada bloco saltado termina com um valor menor do que o alvo, por isso nenhum bloco anterior pode conter uma correspondência, e o percurso começa no início do bloco.

Os meus números são enviados para algum lado?

Não. A pesquisa corre no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor