Pular para o conteúdo

Busca binária

Aula 2 de 8 · 5 min

Busca binária

Passo 1 de 7

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

A busca binária exige que a entrada seja: