O algoritmo de busca binária considera um vetor ordenado de n elementos para realizar a varredura dos elementos, por isso é possível implementar um al...

JUSTIFICATIVA A afirmativa I é CORRETA. A busca binária requer que a lista esteja ordenada em ordem crescente. Já a busca sequencial (ou linear) não traz esta exigência, pois chega a examinar cada item na lista. O tempo de execução da busca sequencial (ou linear) no pior dos casos, é, portanto, proporcional ao tamanho (n) da lista. Portanto, para valores pequenos de n, o custo adicional de ordenar a lista pode não compensar. Em outras palavras, a busca sequencial pode vir a ser mais rápida do que a busca binária. Ressalta-se que embora possam existir exceções, ainda assim o algoritmo de busca binária é considerado um algoritmo mais eficiente do que aquele que utiliza a busca sequencial. A afirmativa II é INCORRETA. Cada sublista a ser examinada tem tamanho igual ao tamanho da metade da lista anterior, portanto as comparações requeridas começam com uma lista de tamanho n/2, depois n/4, depois n/8, depois n/16 e assim sucessivamente enquanto o elemento procurado não tiver sido encontrado, e a lista não for vazia. A afirmativa III também é INCORRETA. Em se tratando de uma lista de tamanho n , o número máximo de comparações requeridas é dado por lg(n), considerando-se que lg (n) representa o logaritmo de n na base 2. No pior caso, ao fracionar a lista em uma quantidade de vezes suficiente, chega-se a uma lista formada por um só elemento, portanto ele será ou não o elemento procurado e o processo chega ao fim. A quantidade de comparações realizadas ao chegar neste ponto é i, em que n/(2^i) = 1 ( n dividido por 2 elevado a i é igual a 1). Ao isolar i , temos i = lg(n) , portanto o número máximo de comparações é o logaritmo na base 2 do número de elementos na lista, dado por n . A afirmativa IV é CORRETA, pois não sendo achado elemento procurado, a busca binária elimina metade dos itens que restam a cada comparação.