Busca binária
Passo 1 de 7
alvo16tentativas0
mid
2
5
8
12
16
23
31
42
lo
hi
O array está ordenado, então o elemento do meio diz em qual metade o alvo não pode estar.
A ideia
Em dados ordenados, compare o alvo com o elemento do meio e jogue fora a metade que não pode contê-lo. Repita até sobrar um candidato. Essa divisão pela metade dá O(log n).
Exemplo do mundo real
Achar “Nadia” nos contatos do celular. Você nunca rola desde o A; pula perto do meio, cai em algum lugar perto do M e na hora ignora tudo o que vem antes. Dois ou três pulos depois, você chegou.
O código
Sua vez
Preencha a lacuna.
nums = [1, 3, 5, 7, 9]
lo, hi = 0, 4
mid = (lo + hi) // 2
# nums[mid] is 5 and the target is 9 -> search right
lo = ___Mini quiz
1 / 3