GabaritoC — Certo
Gabarito: letra C (Certo). A busca binária exige que o vetor esteja previamente ordenado porque o algoritmo funciona dividindo repetidamente o intervalo de busca ao meio e comparando o elemento procurado com o elemento do meio — essa comparação só permite descartar metade do vetor se a ordem dos elementos for conhecida. Sem a ordenação, o algoritmo pode retornar "não encontrado" mesmo quando o elemento existe, ou retornar um índice incorreto.
A busca binária é um dos algoritmos de busca mais eficientes, com complexidade de tempo O(log n), mas essa eficiência tem um custo: ela depende de uma pré-condição fundamental. O vetor precisa estar ordenado (em ordem crescente ou decrescente, conforme a implementação). Isso contrasta com a busca linear, que percorre o vetor elemento por elemento e funciona em qualquer ordem, mas com complexidade O(n).
Vamos entender o porquê. O algoritmo da busca binária funciona assim: você compara o elemento procurado com o elemento do meio do vetor. Se for igual, encontrou. Se o procurado for menor que o do meio, você descarta a metade direita e repete o processo na metade esquerda. Se for maior, descarta a metade esquerda e repete na direita. Esse descarte só é válido se você tiver certeza de que, por exemplo, todos os elementos à esquerda do meio são menores que o elemento do meio. Essa certeza só existe se o vetor estiver ordenado.
Imagine um vetor desordenado: [5, 2, 8, 1, 9]. Se você procurar o número 8, o elemento do meio é 2. Como 8 > 2, você descartaria a metade esquerda e procuraria na direita ([8, 1, 9]). Mas o 8 está na metade esquerda! O algoritmo falharia. Por isso, a ordenação é um requisito de correção, não apenas de eficiência.
A pegadinha que a banca explora aqui é justamente a tentação de achar que a busca binária é um algoritmo "universal" que funciona em qualquer vetor. O candidato que não domina o conceito pode marcar "Errado" pensando que o algoritmo se adapta a qualquer situação. Mas a verdade é que a ordenação é a condição sine qua non para o funcionamento correto da busca binária.
A banca quer que você confunda busca binária com busca linear. A busca linear não exige ordenação, mas a binária exige. Se a questão dissesse "busca linear", a resposta seria "Errado". Aqui, como é busca binária, a resposta é "Certo". Fique atento ao nome do algoritmo!
A afirmação está correta. A busca binária é um algoritmo de busca que, para funcionar corretamente e de forma eficiente, exige que o vetor esteja previamente ordenado. O algoritmo compara o elemento procurado com o elemento do meio do vetor e, com base nessa comparação, descarta metade do vetor a cada iteração. Esse descarte só é possível porque a ordenação garante que todos os elementos de um lado são menores (ou maiores) que o elemento do meio. Sem a ordenação, o algoritmo pode retornar resultados incorretos, pois a premissa de que os elementos estão em ordem é violada.
A afirmação está errada. Ela nega o pré-requisito fundamental da busca binária. A busca binária não funciona corretamente em um vetor desordenado. Se o vetor não estiver ordenado, o algoritmo pode falhar ao encontrar um elemento que existe, ou retornar um índice incorreto. A ordenação é uma condição necessária para a correção do algoritmo, não apenas para sua eficiência. A busca linear, por outro lado, não exige ordenação, mas é menos eficiente (O(n) contra O(log n)).
Gabarito: letra C (Certo).
Link permanente: /questoes/qg603667