MO417 - Questão para a prova oral

Número: 2009-008

Enunciado: A busca binária é um algoritmo de busca em vetor bastante eficiente, porém, requer que este vetor esteja ordenado. Por isso, em alguns casos, dependendo do número de buscas que serão realizadas, é mais interessante utilizar a busca sequencial. Considerando isso, em qual dos seguintes casos, em um vetor com n elementos não necessariamente ordenados, é preferível utilizar a busca sequêncial a ordená-lo e utilizar a busca binária?

1. Quando o número de buscas é inferior a log n
2. Quando o número de buscas é proporcional a n
3. Quando o número de buscas é proporcional a n²
4. Quando o número de buscas é proporcional a n³
5. NDA

Ideia original de: Raoni Florentino da Silva Teixeira