Um algoritmo para pesquisar por um dado valor x em grandes arrays ordenadas, compara por cada elemento do array até que, um maior ou igual a x seja encontrado. Quando um valor maior é encontrado, o algoritmo compara x com os dois elementos anteriores. Se a array estiver ordenada por ordem ascendente, qual das seguintes expressões descreve os casos em 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 dois algoritmos de busca distintos: um algoritmo de busca linear com saltos (passo 3) versus a clássica pesquisa binária. Para determinar qual é mais eficiente em quais cenários, precisamos analisar a complexidade computacional de cada um.

Pesquisa Binária:
Este algoritmo divide o espaço de busca pela metade a cada iteração. Sua complexidade é logarítmica, denotada como O(\log n).

• Exemplo: Em um array com $1.000.000$ elementos, a pesquisa binária realiza cerca de \log_2(1.000.000) \approx 20 comparações no máximo.

Algoritmo do Enunciado (Busca com Saltos):
Este algoritmo avança no array pulando de 3 em 3 posições ($0, 3, 6, \dots$). Sua complexidade é linear, mas com um fator constante, denotada como O(n/3) ou simplesmente O(n).

• No pior caso (elemento no final ou inexistente), ele fará cerca de n/3 comparações.
• No melhor caso (elemento no início), ele encontra o valor imediatamente após poucos saltos.

Análise dos Casos

Para entender quando o algoritmo de saltos é superior, devemos comparar o custo relativo dependendo da posição do elemento x:

• Caso A (Elemento no Início): Se x está nas primeiras posições (índices 0, 1 ou 2), o algoritmo de saltos encontrará o valor em apenas 1 ou 2 comparações. Já a pesquisa binária continuaria calculando o ponto médio do array inteiro, gastando \approx \log n comparações. Para n grande, $2 < \log n$.
• Caso B (Elemento no Meio): A pesquisa binária já estaria a meio caminho. O algoritmo de saltos teria percorrido n/6 posições. Como n/6 \gg \log n para arrays grandes, a binária vence.
• Caso C (Elemento no Fim): O algoritmo de saltos percorreria quase todo o array (n/3). A pesquisa binária ainda usaria \log n. A diferença é abismal.

Portanto, a única situação em que o algoritmo descrito utiliza menos comparações que a pesquisa binária é quando o valor procurado está localizado muito cedo no array, antes que o custo logarítmico da divisão sucessiva supere o custo direto dos primeiros passos lineares.