Seja um vetor com inteiros com 400 inteiros distintos e ordenados em forma crescente, qual é o número máximo de iterações necessárias para encontrar um elemento qualquer do vetor caso seja utilizado o algoritmo de busca binária?
Soluções para a tarefa
No caso temos que com 9 interações pode-se encontrar qualquer elemento em um vetor com 400 inteiros.
Isso porque, numa busca binária, tendo em vista que os números do vetor estão em ordem crescente o algorítimo sempre fará divisões por 2 até que o resultado seja obtido.
Logo, para alcançar um número basta pegar a quantidade de elementos que há num vetor, ou seja, 400, e ir dividindo por 2 até que chegue a 1 e assim ir contando as iterações.
Logo, vamos ter que:
400/2 = 200 (1 iteração)
200/2 = 100 (2 iterações)
100/2 = 50 (3 iterações)
50/2 = 25 (4 iterações)
25/2 = 13 (aqui temos que há uma divisão do vetor por 2, um vetor 12 e outro de 13 elementos, assim temos que há 5 iterações.)
13/2 = 7 (igual a situação anterior) (6 iterações)
7/2 = 4 (idem a situação anterior) (7 iterações)
4/2 = 2 (8 iterações)
2/2 = 1 (9 iterações)
Assim, chegamos ao final com 9 iterações.
espero ter ajudado!
Resposta:
C) 9
Explicação passo a passo: