Algoritmos e Estrutura de Dados · FGV · 2022 | Questão sqc-fg055282

Busca Binária - Complexidade no Pior Caso

Gabarito: letra A. A busca binária em um array ordenado divide o intervalo de busca pela metade a cada comparação, resultando em, no máximo, $\log_2 N$ acessos (comparações) no pior caso, onde $N$ é o número de elementos. Essa é a complexidade assintótica $O(\log N)$ .

A questão cobra o conhecimento fundamental sobre a busca binária: a cada passo, descarta metade dos elementos restantes. Portanto, o número máximo de comparações é a altura de uma árvore binária de busca balanceada, que é $\lceil \log_2 (N+1) \rceil$ , ou seja, da ordem de $\log_2 N$ .

Alternativa A — ✅ Correta ⟵ GABARITO

A expressão $\log_2 N$ representa corretamente a ordem de grandeza do número de acessos no pior caso. Para $N=1.000.000$ , seriam cerca de 20 comparações, enquanto uma busca linear exigiria até 1 milhão.

Alternativa B — ❌ Incorreta

A expressão $\log_2 N \cdot N$ (ou $N \log N$ ) corresponde à complexidade de algoritmos de ordenação como Merge Sort, não da busca binária. Confunde-se o custo da busca com o custo de ordenação. O erro é trocar o conceito (troca_conceito).

Alternativa C — ❌ Incorreta

$N$ é a complexidade da busca linear (sequencial) no pior caso. Na busca binária, o número de comparações é logarítmico, não linear. A banca apresenta aqui um distrator clássico: o candidato que não conhece a busca binária pode pensar que é necessário percorrer todos os elementos. Generalização indevida (generalizacao).

Alternativa D — ❌ Incorreta

$N/2$ também representa uma complexidade linear (constante * N). Embora seja a média de comparações na busca linear, no pior caso da busca binária continua sendo $\log_2 N$ . A alternativa sugere que seriam necessárias metade das comparações, o que não é verdade para o pior caso. Fora do escopo (fora_do_escopo), pois não corresponde ao comportamento da busca binária.

Alternativa E — ❌ Incorreta

$N^2$ é uma complexidade quadrática, típica de algoritmos como Bubble Sort (no pior caso) ou busca em matriz. Totalmente incompatível com a busca binária. Generalização indevida (generalizacao).

PEGA ESSA DICA!

Para fixar, lembre-se: a busca binária reduz o problema pela metade a cada passo → $\log_2 N$ comparações. Compare com a busca linear ( $N$ ) e com a ordenação por comparação ( $N \log N$ ). Em provas, a banca frequentemente coloca $N$ como distrator; elimine-o primeiro.

Gabarito: letra A — a única que expressa a ordem logarítmica correta.