Questão de Tecnologia da Informação · FGV TRF1 2024 (nº 42)

A busca binária é um algoritmo eficiente para encontrar um item em uma lista ordenada que funciona dividindo repetidamente a lista ao meio até encontrar o elemento ou determinar que ele não está presente.

• (A) Incorreta: O(n) representa a complexidade de uma busca linear, onde cada elemento da lista é verificado um por um, o que é muito menos eficiente que a busca binária. Armadilha da banca: Esta é a alternativa mais tentadora para quem confunde busca binária com busca linear, ou para quem pensa que, por estar em uma lista de 'n' elementos, a complexidade deve ser 'n'. A busca binária não verifica todos os elementos.
• (B) Incorreta: O(n log n) é a complexidade típica de algoritmos de ordenação eficientes, como Merge Sort ou Quick Sort, e não de busca.
• (C) Correta: A busca binária reduz o espaço de busca pela metade a cada passo. O número de vezes que você pode dividir 'n' pela metade até chegar a 1 é logaritmo de 'n' na base 2 (log₂n), resultando em uma complexidade de tempo logarítmica.
• (D) Incorreta: O(n^2) é uma complexidade muito alta, geralmente associada a algoritmos ineficientes que envolvem laços aninhados, como alguns algoritmos de ordenação simples.
• (E) Incorreta: O(1) significa tempo constante, ou seja, a operação leva o mesmo tempo independentemente do tamanho da entrada, o que não é o caso da busca binária, que precisa de algumas comparações.