Padrão 2: Busca binária modificada (array girado)
E se alguém pegasse o array ordenado e o girasse num ponto qualquer?
[0,1,2,4,5,6,7]vira[4,5,6,7,0,1,2]. Ainda dá para manter o O(log n) — o truque é descobrir, a cada passo, qual metade ainda está ordenada.
Tente primeiro: Search in Rotated Sorted Array
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Um array ordenado foi girado em algum pivô desconhecido (ex.: [0,1,2,4,5,6,7] virou [4,5,6,7,0,1,2]). Dado nums e target, retorne o índice de target ou -1. Espera-se O(log n).
Exemplo: nums = [4,5,6,7,0,1,2], target = 0 → 4.
Tentou? A saída fácil é varrer tudo — O(n) — e ignorar que o array é "quase ordenado". A teoria abaixo recupera o O(log n) mesmo com a rotação.
A teoria: uma das metades sempre está ordenada
Eis a observação que destrava tudo: por mais que o array tenha sido girado,
quando você corta no mid, pelo menos uma das duas metades está
perfeitamente ordenada. Sempre. (A outra contém o "ponto de virada".)
Você descobre qual comparando as pontas:
- Se
nums[left] <= nums[mid], a metade esquerda[left..mid]é ordenada. - Senão, a metade direita
[mid..right]é ordenada.
E aí o pulo do gato: na metade ordenada, você sabe exatamente quais
valores ela contém — então consegue testar se o target cai nela. Se cai, vá
para essa metade; se não, vá para a outra. De qualquer jeito, você descarta
metade — e o O(log n) sobrevive.
mid = meio
se nums[mid] == target → achou
se a metade ESQUERDA é ordenada (nums[left] <= nums[mid]):
se target está em [nums[left], nums[mid]) → vá para a esquerda
senão → vá para a direita
senão (metade DIREITA é ordenada):
se target está em (nums[mid], nums[right]] → vá para a direita
senão → vá para a esquerda
Veja a decisão acontecendo — note como o intervalo ativo pula para o lado onde o alvo pode estar:
Por que continua O(log n)?
A estrutura é a mesma da busca binária clássica: cada iteração faz trabalho O(1) (algumas comparações) e descarta metade do intervalo. O número de iterações continua log₂(n). A rotação só muda como decidimos o lado — não quantas vezes cortamos. O(log n) de tempo, O(1) de espaço.
Exemplo 2 — Find Minimum in Rotated Sorted Array
"Qual o menor elemento do array girado?" O menor é o ponto de virada (o
lugar onde a ordem "quebra"). Mesma filosofia, decisão ainda mais simples:
compare nums[mid] com nums[right].
- Se
nums[mid] > nums[right], a virada está à direita demid→ o mínimo está em[mid+1 .. right]. - Senão,
midainda pode ser o mínimo →[left .. mid].
Repare que aqui usamos left < right e right = mid (sem o −1): estamos
convergindo para uma posição (o mínimo), não testando um valor exato — um
sabor diferente de busca binária. Esses detalhes de fronteira são o que você
treina até virar reflexo.
A lição que generaliza
Busca binária não exige um array totalmente ordenado — exige só que, a cada passo, você consiga decidir com certeza para que lado ir. No array girado, a metade ordenada te dá essa certeza. Sempre que você conseguir responder "o alvo está deste lado ou do outro?" em O(1), busca binária está no cardápio.
🧠 Quiz de fixação
0/41. Ao cortar um array girado no meio, o que é SEMPRE verdade sobre as duas metades?
2. Como saber qual metade está ordenada no array girado?
3. Por que a busca no array girado continua O(log n)?
4. Qual é a condição geral para poder usar busca binária, mesmo sem o array estar totalmente ordenado?
Resumo
- Num array girado, uma das metades sempre está ordenada; descubra qual comparando as pontas e decida o lado por ali.
- O(log n) se mantém: a rotação muda a decisão, não o número de cortes.
- Find Minimum: convirja para a posição do ponto de virada (
left < right,right = mid). - Busca binária exige só decidir o lado com certeza em O(1) — não ordem total.
Começa agora o segundo módulo da seção: bits. Próxima aula, os fundamentos.