Um algoritmo para pesquisar por um dado valor x em grandes arrays ordenadas compara x com cada terceiro elemento do array até que um valor maior ou igual a x seja encontrado. Quando um valor maior ou igual a x é encontrado, o algoritmo compara x com os dois elementos anteriores. Se a array estiver ordenada por ordem ascendente, qual das seguintes expressões descreve de que o algoritmo utiliza menos comparações para encontrar x, que aquelas utilizadas numa pesquisa binária?

Alternativa C - Quando x está muito próximo do início da array

A questão compara a eficiência de uma busca linear escalonada (pula de 3 em 3) com a busca binária padrão. Para entender qual cenário favorece o algoritmo descrito, precisamos analisar a complexidade de ambos.

Análise Comparativa

1. Pesquisa Binária:

• Funciona dividindo o intervalo de busca pela metade a cada passo.
• Sua complexidade é logarítmica: O(\log_2 n).
• Independentemente de onde o valor esteja, no pior caso ela realiza cerca de \log_2 n comparações.

1. Algoritmo Descrito (Busca por Salto/Jump Search):

• O algoritmo pula blocos de tamanho fixo (3 posições).
• Se o valor x estiver na posição i, ele precisará realizar aproximadamente i/3 saltos para chegar à região correta.
• A complexidade depende diretamente da posição do elemento: O(i/k), onde k é o tamanho do salto.

Por que a Alternativa C é correta?

Para que o algoritmo utilize menos comparações que a busca binária, a quantidade de passos lineares deve ser menor que o número logarítmico de passos da busca binária.

• Cenário Próximo ao Início: Se x está no índice 1 ou 10, o algoritmo faz pouquíssimos saltos (ex: verifica índice 3, depois volta 1 casa). O custo é baixo (constante ou quase constante). A busca binária ainda teria que percorrer profundidades logarítmicas para encontrar esse início.
• Cenário Próximo ao Fim: Se x está no final, o algoritmo precisa fazer muitos saltos até chegar lá, tornando-o muito mais lento que a busca binária.

Portanto, a vantagem competitiva do algoritmo ocorre apenas quando o alvo está localizado nos primeiros índices do array, onde o custo linear inicial é inferior ao custo logarítmico da busca binária.