Para resolver problemas de maneira eficiente, pode-se tentar eliminar soluções inviáveis, encurtando o caminho para uma resolução. A busca binária e a busca em árvore binária são dois exemplos de algoritmos que "podam" soluções errôneas. Considerando seus conhecimentos a respeito desses dois algoritmos, avalie as afirmações a seguir.
I - O fato de um vetor já estar ordenado tem total influência no funcionamento da busca binária.
II - A busca binária, quando aplicada em uma lista dinâmica, tem um ganho de desempenho com relação à versão estática.
III – A busca binária, de modo geral, faz log n comparações, onde n é o tamanho do arranjo de busca.
Com base no exposto é possível dizer que é verdadeiro o que se afirma em:
Soluções para a tarefa
Resposta:
Alternativa 4: I e III, apenas.
Explicação:
CORRETO I - O fato de um vetor já estar ordenado tem total influência no funcionamento da busca binária. Pág. 124 do Livro: "A forma mais eficiente de efetuar pesquisa em um arquivo ordenado sem a necessidade de tabelas auxiliares é a busca binária."
ERRADO II - A busca binária, quando aplicada em uma lista dinâmica, tem um ganho de desempenho com relação à versão estática. Pág. 125 do Livro: "Esse algoritmo não pode ser utilizado com listas dinâmicas devido às características da sua estrutura".
CORRETO III – A busca binária, de modo geral, faz log n comparações, onde n é o tamanho do arranjo de busca.
"Log(n), pois cada comparação reduz o número de possíveis candidatos por um fator de 2."
Referências:
https://www.ime.usp.br/~pf/algoritmos/aulas/bubi.html
http://wiki.icmc.usp.br/images/5/55/Aula_busca.pdf
Resposta:
Alternativa 4, I e III apenas.
Explicação:
I - Verdadeira pois essa estratégia funciona apenas em estruturas cujos dados se encontram ordenados;
II - Falso pois esse algoritmo não pode ser utilizado com listas dinâmicas devido às características da sua estrutura;
III - Verdadeira pois a estratégia consiste em comparar o argumento chave ao elemento do meio da tabela.