Questão de Algoritmos e Estrutura de Dados — Algoritmos — IDECAN 2019
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq500350
Banca
IDECAN
Órgão
IF-PB
Ano
2019
Nível
Superior
Cargo
Professor - Informática
Basicamente, existem dois métodos de pesquisa em um vetor de números, a Busca Linear e a Busca Binária. A Busca Binária é mais eficiente do que a Busca Linear, mas ela só funciona se o vetor estiver ordenado. Assinale a alternativa que indique a ordem de complexidade do pior caso da Busca Binária em um vetor de n números ordenados.
AO(n)
BO(n log n)
CO(log n)
DO(1)
EO(n^2)
Revelar gabarito e comentário▾
GabaritoC — O(log n)
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Busca Binária – Complexidade de Pior Caso
Gabarito: letra C. A complexidade do pior caso da Busca Binária em um vetor de n números ordenados é O(log n). Esse desempenho ocorre porque, a cada iteração, o algoritmo divide o espaço de busca pela metade, reduzindo exponencialmente o número de comparações necessárias até encontrar o elemento ou esgotar as possibilidades.
A banca testa o conhecimento das notações assintóticas básicas dos algoritmos de busca. Enquanto a Busca Linear tem complexidade O(n), a Busca Binária aproveita a ordenação do vetor para alcançar eficiência logarítmica.
Alternativa A — ❌ Incorreta
O(n) é a complexidade da Busca Linear (ou sequencial), que percorre todo o vetor no pior caso. Na Busca Binária, o número de comparações é muito menor para grandes valores de n.
Alternativa B — ❌ Incorreta
O(n log n) é a complexidade típica de algoritmos de ordenação eficientes (como Mergesort ou Heapsort), não da busca binária. A busca binária não realiza operações que exijam esse custo.
Alternativa C — ✅ Correta ⟵ GABARITO
A Busca Binária, no pior caso, realiza log₂(n) comparações (arredondando para cima). Isso porque cada passo descarta metade do vetor restante. Formalmente, a complexidade é Θ(log n) e O(log n).
Alternativa D — ❌ Incorreta
O(1) representa tempo constante, independente do tamanho da entrada. A Busca Binária não consegue encontrar um elemento em uma única operação (a menos que o vetor tenha tamanho fixo muito pequeno, mas a notação assintótica considera n variável).
Alternativa E — ❌ Incorreta
O(n²) é característico de algoritmos ineficientes, como Bubble Sort (ordenação) ou busca ingênua em matrizes. Não se aplica à busca binária, que é um dos algoritmos mais eficientes para vetores ordenados.
PEGA ESSA DICA!
Para fixar, lembre-se da relação inversa entre a base 2 e o crescimento: com 1.000 elementos, a busca linear pode exigir 1.000 passos; a binária exige no máximo 10 (pois 2¹⁰ ≈ 1.000). Essa diferença fica ainda mais dramática com milhões de elementos.