Busca Binária em Arrays Rotacionados e Não Ordenados

Um vetor ordenado rotacionado é um vetor ordenado que foi cortado em algum ponto de rotação e teve suas duas partes trocadas. Por exemplo, [4, 5, 6, 7, 0, 1, 2] é o vetor ordenado [0,1,2,4,5,6,7] rotacionado no índice 4. A busca binária padrão falha nesse caso porque o vetor não está mais ordenado globalmente.

A ideia principal é que pelo menos uma metade do vetor está sempre ordenada após qualquer rotação. Sua busca binária precisa identificar qual metade está ordenada antes de decidir para onde mover os limites.

Depois de calcular mid, compare arr[lo] com arr[mid]. Se arr[lo] <= arr[mid], a metade esquerda está ordenada; caso contrário, a metade direita está ordenada. Depois de saber qual metade está ordenada, você pode verificar se o alvo está dentro desse intervalo ordenado e restringir a busca de acordo.

Essa árvore de decisão permite descartar exatamente metade do vetor a cada etapa, mantendo a complexidade O(log n) mesmo em um vetor rotacionado.

Vamos acompanhar search_rotated([4,5,6,7,0,1,2], 0) passo a passo. Inicialmente, lo=0, hi=6, mid=3, arr[mid]=7. O alvo 0 está na metade esquerda ordenada [4..7]? Não, então movemos lo=4. Agora, lo=4, hi=6, mid=5, arr[mid]=1. A metade esquerda [0,1] está ordenada (arr[lo]=0 <= arr[mid]=1). 0 está em [0..1)? Sim, então definimos hi=4. Agora, lo=4, hi=4, mid=4, arr[4]=0 — encontrado no índice 4.

Quando o vetor rotacionado pode conter duplicados (por exemplo, [1,3,1,1,1]), a condição nums[lo] == nums[mid] é ambígua — não é possível saber qual metade está ordenada. A correção segura é incrementar lo (ou decrementar hi) em um e tentar novamente. Isso degrada o tempo no pior caso para O(n), algo que você deve mencionar ao entrevistador.

Um problema relacionado pede o elemento mínimo em um vetor ordenado rotacionado, sem buscar um alvo específico. O mínimo está sempre na metade não ordenada. A cada etapa: se arr[mid] > arr[hi], o mínimo está na metade direita (lo = mid + 1); caso contrário, está na metade esquerda, incluindo mid (hi = mid). Quando lo == hi, você encontrou o mínimo.

A condição arr[lo] <= arr[mid] funciona porque, em um segmento ordenado (ou ordenado sem rotação), o primeiro elemento é sempre o menor. Se arr[lo] <= arr[mid], nenhuma rotação ocorreu dentro de [lo..mid], portanto essa metade está ordenada. A igualdade trata do caso em que lo == mid (um segmento de um único elemento é trivialmente ordenado).

Por outro lado, se arr[lo] > arr[mid], o pivô da rotação deve estar entre lo e mid, o que significa que a metade direita [mid..hi] é o segmento ordenado contínuo.

Buscar em um vetor ordenado rotacionado usando busca binária continua levando O(log n) de tempo e usando O(1) de espaço, porque ainda reduzimos o espaço de busca pela metade a cada iteração. A única diferença em relação à busca binária clássica é uma verificação adicional, de tempo constante, para identificar qual metade está ordenada.

Com duplicados, o pior caso degrada para O(n), porque podemos incrementar lo em apenas um a cada etapa. Mencione explicitamente essa compensação — isso mostra que você considera casos-limite além do caminho ideal.

LeetCode 33, 'Busca em vetor ordenado rotacionado', é a forma canônica desse problema. As restrições garantem que não há duplicados e que existe exatamente uma rotação. A solução é a função search_rotated que escrevemos anteriormente. Pontos importantes para a entrevista: sempre declare a suposição de que não há duplicados, verifique suas desigualdades com um exemplo concreto no limite e confirme que o índice retornado está correto tanto nos casos em que o elemento é encontrado quanto nos casos em que não é encontrado.

LeetCode 153, 'Encontrar o mínimo em um vetor ordenado rotacionado', pede o mínimo sem duplicados. A abordagem consiste em comparar arr[mid] com arr[hi] (e não com arr[lo]) para determinar de que lado está o mínimo. Se arr[mid] > arr[hi], o mínimo está à direita; caso contrário, está em mid ou à esquerda. Isso converge para o mínimo em O(log n).

Depois que você consegue encontrar o elemento mínimo, também conhece a contagem de rotações: o índice do mínimo indica exatamente quantas posições o vetor foi rotacionado para a direita. Por exemplo, em [4,5,6,7,0,1,2], o mínimo está no índice 4, portanto o vetor foi rotacionado 4 posições.

Conhecer o pivô permite aplicar a busca binária padrão tratando os índices módulo n: real_idx = (mid + pivot) % n. Essa formulação alternativa pode simplificar o raciocínio ao trabalhar com estruturas indexadas circularmente.

Quando encontrar um problema com um vetor rotacionado em uma entrevista, siga esta árvore de decisão. Primeiro, determine se precisa encontrar um alvo ou encontrar o mínimo. Para encontrar um alvo, use a abordagem de identificação da metade ordenada. Para encontrar o mínimo, compare mid com hi. Se houver possibilidade de duplicados, mencione o pior caso O(n) e adicione a alternativa de redução dos limites.

Pratique acompanhando seu código nos três exemplos clássicos: sem rotação, com uma rotação e com rotação que coloca o mínimo na última posição.

Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.

Nesta lição, você aprendeu: um vetor ordenado rotacionado sempre tem pelo menos uma metade ordenada, compare arr[lo] com arr[mid] para identificar qual metade está ordenada antes de decidir onde buscar e para encontrar o mínimo, use arr[mid] em relação a arr[hi] para localizar o pivô da rotação. A seguir, exploraremos as variantes de busca binária de limite inferior e limite superior.