Questão de Auditoria em Tecnologia da Informação · FCC Prefeitura de São Luís 2018 (nº 86)

A função teste implementa uma busca binária, um algoritmo eficiente para encontrar um valor em uma lista ordenada. Ela funciona dividindo repetidamente o intervalo de busca pela metade, comparando o valor procurado com o elemento do meio e descartando a metade onde o valor não pode estar.

• (A) Incorreta: O valor 3 é o primeiro índice j calculado na busca (p[3] = 88), mas não é o valor procurado nem o resultado final.
• (B) Incorreta: O índice 6 (p[6] = 401) não é alcançado nem corresponde ao valor procurado.
• (C) Incorreta: O valor 8 é o tamanho n do vetor, não um índice válido para retorno da função nem o resultado da busca.
• (D) Incorreta: O valor 2 foi um valor intermediário de d (limite superior do intervalo de busca), mas não o resultado final.
• (E) Correta: A função retorna -1 porque o valor 9 não está presente no vetor p. A busca binária funciona da seguinte forma:
  1. Início: y = 0, d = 7. j = (0+7)/2 = 3. p[3] = 88. Como 88 > 9, o limite superior d se torna 3-1 = 2.
  2. Próxima iteração: y = 0, d = 2. j = (0+2)/2 = 1. p[1] = 10. Como 10 > 9, o limite superior d se torna 1-1 = 0.
  3. Próxima iteração: y = 0, d = 0. j = (0+0)/2 = 0. p[0] = 7. Como 7 < 9, o limite inferior y se torna 0+1 = 1.
  4. Próxima iteração: y = 1, d = 0. A condição do laço (y <= d) (1 <= 0) é falsa, e o laço termina.
  5. Como o elemento não foi encontrado, a função retorna -1. A armadilha aqui é que, embora o vetor esteja ordenado e 9 esteja "entre" 7 e 10, a busca binária só retorna o índice se o elemento for exatamente encontrado. Caso contrário, ela indica que não foi localizado.