Algoritmo de busca de salto para arrays

Majoritariamente, quando desenvolvedores de software debatem sobre operações de busca em estruturas de dados como arrays, os algoritmos de busca linear e busca binária são os mais citados durante as suas discussões. Isso se justifica por diversos motivos, entre os quais cabe salientar a facilidade de implementação e a performance de execução constatada nas respectivas funções de pesquisa.

Todavia, o catálogo de algoritmos voltado para a procura de elementos não se limita à busca linear e busca binária. A não tão popular busca de salto é uma terceira opção referenciada com pouca frequência na literatura e muitas vezes esquecida no dia a dia pelos programadores.

Embora a busca de salto não seja difundida na mesma proporção do que os seus pares, a aplicabilidade do algoritmo permanece sendo relevante, dependendo, sobretudo, da quantidade de itens a serem pesquisados e das eventuais restrições de tempo estipuladas nos requisitos do sistema.

Entendendo o algoritmo

O nome do algoritmo possui uma pista substancial no que diz respeito à sua lógica e ao seu funcionamento. De maneira essencial, a proposta da busca de salto ou jump search, consiste na checagem da menor parcela possível de itens, avançando a pesquisa em etapas fixas. Ou seja, pulando explicitamente alguns elementos do vetor de input, que obrigatoriamente deve estar ordenado. 

Para exemplificar, suponha a existência de um array qualquer arr de tamanho n, e um bloco de tamanho m. Os índices varridos obedeceriam à sequência arr[0], arr[m], arr[2m] até arr[km]. Se porventura o item x buscado na estrutura estivesse dentro do intervalo arr[km] < x < arr[(k+1)m], bastaria que uma pesquisa linear fosse feita a partir do índice km para localizar a sua posição.

Traduzindo a teoria em prática, considere que o vetor arr armazene dez números [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]. A busca de salto encontrará o elemento 17 através dos passos listados a seguir, assumindo que o bloco pulado pelo algoritmo é de três itens.

1. Pular do índice 0 para o índice 3.
2. Pular do índice 3 para o índice 6.
3. Pular do índice 6 para o índice 9.
4. Dado que o número no índice 9 supera o valor procurado de 17, a função retorna para o índice 6.
5. Partindo do índice 6, a função realiza uma busca linear para encontrar o número 17.

Conforme mencionado, neste cenário hipotético, a busca de salto fez um pulo de três itens por iteração. Vale frisar que esse tamanho do salto apresenta um raciocínio matemático, portanto não sendo aleatório.

Na pior das situações, o algoritmo precisa fazer n/m saltos, vide o exemplo anterior (10/3). E, se o último elemento do array for maior do que o número pesquisado, o método de pesquisa faz mais m-1 verificações no contexto da busca linear. Isso tudo resulta em ((n/m) + m-1) comparações necessárias para achar o item desejado. Por consequência, o valor da função é mínimo quando m = √n, que caracteriza justamente a fórmula do tamanho do salto.

Analisando a implementação do algoritmo

A principal vantagem da busca de salto reside no fator da complexidade de tempo. Diferente da busca linear, a sua função de pesquisa executa em complexidade de raiz quadrada de tempo. Isso viabiliza uma performance notavelmente superior à medida que o input processado cresce de tamanho.

O ponto chave que garante um melhor desempenho do algoritmo está no tamanho do salto. Sem ele, assim como a busca linear, a busca de salto percorreria todos os elementos do vetor. Porém, com a sua aplicabilidade, a busca de salto ignora boa parte dos itens, o que resulta em menos checagens na estrutura.

De modo detalhado, o algoritmo em questão completa as seguintes etapas com o intuito de encontrar a posição do número pretendido.

1. A variável salto é declarada para definir qual será o tamanho do salto usado pela função.
2. A variável saltoAnterior é declarada para armazenar a posição do salto precedente à execução da busca linear.
3. Enquanto o número pesquisado x for maior que o número presente no índice do salto atual, ou até mesmo no índice final do array arr (caso os saltos tenham sido esgotados), a função continua pulando os elementos da estrutura de acordo com o tamanho do salto. O método retorna o valor 'menos um' somente se os saltos excederem os limites do vetor, indicando assim que x não foi localizado.
4. Após o último salto, a função utiliza o algoritmo da busca linear para determinar se o número x está no array arr. Dessa forma, a variável saltoAnterior é incrementada a cada laço. Se a pesquisa atingir o término do vetor, isto significa que x não foi encontrado, e o método retorna o valor 'menos um'.
5. Contudo, se a busca linear for interrompida pela condição arr[saltoAnterior] < x, isto quer dizer que possivelmente o elemento no índice saltoAnterior e o número x procurado são equivalentes. Se isso for verdade, a função retorna a posição acumulada em saltoAnterior. Senão, retorna o valor 'menos um'.

Comparando o desempenho do algoritmo com a busca linear

A busca de salto está no meio do caminho entre a busca linear e a busca binária. No que tange a complexidade de tempo, o algoritmo ostenta uma performance de raiz quadrada. Em contrapartida, de maneira óbvia, a busca linear dispõe de uma complexidade linear de tempo, e a busca binária de uma complexidade logarítmica de tempo.

Sob a óptica do espaço auxiliar de memória, a busca de salto se iguala às implementações não recursivas da busca linear e busca binária, usufruindo de uma complexidade constante neste quesito. Isso porque o algoritmo depende apenas de laços de repetição, atribuições de variáveis simples e validações de condicionais.

Método	Input	Média de tempo	Espaço alocado
MétodoBuscaSalto	InputInt32[10]	Média de tempo7.071 ns	Espaço alocado-
MétodoBuscaLinear	InputInt32[10]	Média de tempo4.634 ns	Espaço alocado-
MétodoBuscaSalto	InputInt32[100]	Média de tempo17.442 ns	Espaço alocado-
MétodoBuscaLinear	InputInt32[100]	Média de tempo42.891 ns	Espaço alocado-
MétodoBuscaSalto	InputInt32[200]	Média de tempo19.815 ns	Espaço alocado-
MétodoBuscaLinear	InputInt32[200]	Média de tempo75.081 ns	Espaço alocado-
MétodoBuscaSalto	InputInt32[300]	Média de tempo29.594 ns	Espaço alocado-
MétodoBuscaLinear	InputInt32[300]	Média de tempo104.339 ns	Espaço alocado-
MétodoBuscaSalto	InputInt32[1000]	Média de tempo41.304 ns	Espaço alocado-
MétodoBuscaLinear	InputInt32[1000]	Média de tempo334.865 ns	Espaço alocado-

O quadro acima mostra um comparativo de execução dos algoritmos da busca de salto e da busca linear. Em um teste com somente dez elementos no vetor de input, a busca linear leva vantagem por três nano segundos. Entretanto, a busca de salto passa a ser mais eficiente no momento em que o input aumenta para cem itens, auferindo um ganho de vinte e cinco nano segundos.

A diferença de tempo se acentua no processamento de duzentos, trezentos e mil elementos, registrando um hiato entre os algoritmos de cinquenta e seis, setenta e cinco, e duzentos e noventa e três nano segundos, respectivamente.

O código-fonte completo dos algoritmos e os detalhes extras acerca do desempenho de cada um deles estão disponíveis no meu repositório do Github.