Acerca das estruturas de dados multimídias e dos algoritmos de ordenação e busca, julgue o item a seguir. A busca binária pode ser aplicada com eficiência em qualquer estrutura de

Gabarito

Errado

Comentário do professor

A afirmação está errada porque a busca binária exige que os dados estejam ordenados e que seja possível obter o elemento do meio de forma eficiente. Sem ordenação, comparar com o "meio" não permite eliminar metade do espaço de busca.

Em vetores e arrays, com acesso aleatório, a busca binária tem custo \(O(\log n)\). Em listas encadeadas, mesmo tentando aplicar a ideia, localizar o meio exige travessia, tornando o processo muito mais caro: cada passo para achar o meio é \(O(n)\), repetido \(O(\log n)\) vezes, resultando aproximadamente em \(O(n\log n)\).

Portanto, não é correto afirmar que a busca binária funciona eficientemente em qualquer estrutura linear. É preciso que os dados sejam ordenados e que o acesso ao elemento do meio seja eficiente.