Busca Binária – Pré-requisito e Complexidade
Gabarito: letra B. Para que a Busca Binária seja aplicada com sucesso, o vetor deve estar ordenado, e sua complexidade de tempo no pior caso é O(log n). Isso porque o algoritmo divide repetidamente o espaço de busca pela metade, exigindo que os elementos estejam em ordem crescente (ou decrescente) para que a comparação com o elemento central seja significativa.
A banca testa o conhecimento básico do algoritmo: confundir o pré-requisito (ordenado vs. desordenado) ou a complexidade (log n vs. linear) são os erros mais comuns.
Característica | Busca Binária | Busca Linear |
|---|
Pré-requisito | Vetor ordenado | Nenhum |
Complexidade pior caso | O(log n) | O(n) |
Alternativa A — ❌ Incorreta
Afirma que o vetor deve estar desordenado e a complexidade é O(n). O erro é duplo: a busca binária exige ordenação, e O(n) é a complexidade da busca linear, não da binária. A alternativa troca o pré-requisito e a complexidade com o algoritmo de busca sequencial.
Alternativa B — ✅ Correta ⟵ GABARITO
Correta ao afirmar que o vetor deve estar ordenado e que a complexidade no pior caso é O(log n). A cada comparação, o tamanho do espaço de busca é reduzido à metade, resultando em tempo logarítmico.
Alternativa C — ❌ Incorreta
Afirma que o vetor deve conter apenas números inteiros (pré-requisito falso) e que a complexidade é O(log n) (correta). A busca binária funciona com qualquer tipo de dado que suporte comparação de ordem (números, strings, etc.), não apenas inteiros. O erro está no pré-requisito restritivo.
Alternativa D — ❌ Incorreta
Afirma que o vetor deve ser dinâmico e a complexidade é O(n²). A busca binária não exige que o vetor seja dinâmico (pode ser estático) e sua complexidade é O(log n), não O(n²). A alternativa erra ambos os pontos.
Alternativa E — ❌ Incorreta
Afirma que o vetor deve possuir tamanho par e complexidade O(n). Não há qualquer exigência de paridade no tamanho; a busca binária funciona com vetores de qualquer tamanho. A complexidade também está errada (deveria ser O(log n)).
Gabarito: letra B.