-
Pesquisa binária: Precisa estar ordenada! Complexidade O (log2 n) no pior caso. Número máximo de iterações para localizar um valor: [log2n] +1
A busca binária procura sempre na metade do vetor pelo valor.
- Se o valor foi encontrado termina
- Se o valor é menor repete a busca na metade superior do vetor
- se o valor é maior repete a busca na metade inferior do vetor
No caso da questão, o array tem 10 posições, logo, temos log de 10 na base 2 que dá 3,333... Aproximando, gabarito D.
-
2^3 = 8
2^4 = 16
Em alguns casos, daria para concluir a bsuca com 3 movimentos, mas não sempre. Como ele pede o menor número, acho que ele quer saber se é possível determinar a ausência de um número no array com 3 movimentos. Sim, é possível em alguns casos, mas para que tenhamos SEMPRE certeza de que o número não está presente, são necessários 4 movimentos. Errei, marquei 4, na hora que lí entendi de outra forma.
-
Além da forma explicada no comentário da [Liliane Viana], que tem embasamento teórico no livro de Fonte: Estruturas de dados e seus algoritmos / Jayme Luiz Szwarcfiter, Lilian Markenzon. - 3.ed. [Reimpr.]. - Rio de Janeiro : LTC, 2015.
Existe uma maneira mais fácil e simples de fazer a questão, que é a seguinte:
Como o array tem tamanho 10 e a pesquisa binária consistem em sucessivas divições do array por 2, teremos:
10/2 = 5 (comparação 1)
5/2 = 2 (comparação 2)
2/2 = 1 (comparação 3)
-
Força Guerreiro!!!!!!