-
750 / 2 = 375 (1)
375 / 2 = 187 (2)
187 / 2 = 93 (3)
93 / 2 = 46 (4)
46 / 2 = 23 (5)
23 / 2 = 11 (6)
11 / 2 = 5 (7)
5 / 2 = 2 (8)
2 / 2 = 1 (9)
O número máximo de iterações para que o elemento seja encontrado ou seja detectado que esse número não se encontra no vetor não é 9? Por que 10?
-
@Marcelinho:
.
2 / 2 = 1 (9) <= aqui ele tem que fazer DUAS comparações, porque ele precisa saber se o elemento existe ou não, e não somente a posição. Então ele tem que comparar os dois elementos que restam pra saber se um deles é o elemento procurado.
.
Do jeito que você fez a conta você assumiu que o elemento de fato existe no conjunto e que é só achar a posição dele, quando na verdade você não sabe se ele existe ou não.
-
A posição central do vetor não pode ser um número quebrado, portanto se soma uma posição ao meio.
750 / 2 = 375 ----------- (1)
375 / 2 = 187 + 1 ------ (2)
188 / 2 = 94 ------------- (3)
94 / 2 = 47 + 1 --------- (4)
48 / 2 = 24 -------------- (5)
24 / 2 = 12 -------------- (6)
12 / 2 = 6 ---------------- (7)
6 / 2 = 3 + 1 ------------- (8)
4 / 2 = 2 ------------------ (9)
2 / 2 = 1 ----------------- (10)
https://www.youtube.com/watch?v=gpCnXU-1FNA
-
É possível fazer dessa forma também: número de iterações para buscar com a busca binária
é da complexidade de log2 (N), arredondado para cima.
log2 (750). Ao aplicarmos a definição de logaritmo:
2^x = 750
Poderíamos calcular trocando a base do log, resolvendo tudo,... mas sabendo que: 2^9 = 512 e 2^10 = 1024,
é possível inferir que x está entre 9 e 10. Como arredondamos para cima, nº máx de iterações será igual a 10.