Alternativa C - A lista está em ordem alfabética
Introdução ao Problema
A questão aborda um conceito fundamental de Algoritmos e Estruturas de Dados: a Pesquisa Binária (também conhecida como Busca Binária ou Binary Search).
O objetivo é encontrar um elemento específico (X) dentro de uma lista ordenada de nomes. Para que esse algoritmo funcione corretamente, existem regras rígidas sobre o estado dos dados antes da busca ser iniciada.
O Princípio da Pesquisa Binária
A pesquisa binária funciona através do método de "dividir e conquistar". O algoritmo compara o valor procurado com o elemento central da lista. Com base nessa comparação, ele descarta metade das possibilidades restantes.
Para isso, é estritamente necessário que os dados estejam organizados. Se não houver uma ordem definida, o algoritmo não consegue saber se deve procurar na metade esquerda ou direita da lista após comparar com o meio.
Análise das Alternativas
Vamos analisar cada opção para entender por que apenas uma é a pré-condição correta:
- a. Não existem nomes duplicados na lista: Incorreto. A pesquisa binária pode lidar com elementos duplicados. Embora possa retornar qualquer uma das posições onde o nome existe, a existência de duplicatas não invalida o funcionamento do algoritmo.
- b. O número de nomes na lista, N, é grande: Incorreto. Embora a pesquisa binária seja muito eficiente para listas grandes, ela pode ser aplicada em listas pequenas também. O tamanho não é uma pré-condição funcional, mas sim uma vantagem de desempenho.
- c. A lista está em ordem alfabética: Correto. Esta é a regra de ouro da pesquisa binária. Como trabalhamos com strings (nomes), a lista deve estar organizada alfabeticamente (ordem crescente ou decrescente) para que a lógica de divisão funcione.
- d. O nome X não está definitivamente na lista: Incorreto. A busca serve justamente para descobrir se o nome existe ou não. Assumir que ele não existe tornaria a busca desnecessária.
- e. O nome X está próximo do meio da lista: Incorreto. A localização exata do nome é o que estamos tentando descobrir. Assumir sua posição invalidaria a necessidade de pesquisar.
Conclusão
A eficiência e a correção da pesquisa binária dependem exclusivamente da organização prévia dos dados. Portanto, a única pré-condição obrigatória entre as opções apresentadas é que a lista esteja ordenada.
Resumo:
A alternativa C é a correta porque a Pesquisa Binária exige que o vetor ou lista esteja previamente ordenado para permitir a eliminação de metades do espaço de busca baseada na comparação de valores.