24 de Março
Busca em array rotacionado
Como adaptar busca binaria quando a ordem continua la, mas foi quebrada por uma rotação.
Busca Intermediario 22 min TypeScript
Dado um array de inteiros distintos nums, que estava ordenado em ordem crescente e depois foi rotacionado em um ponto desconhecido, retorne o indice de target.
Se target não existir, retorne -1.
Sua solução deve rodar em O(log n).
Exemplo:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
O que perceber antes de codar
- A rotação não destruiu toda a ordem. Ela só criou um corte.
- Em cada iteração, um dos lados continua ordenado normalmente.
- A decisão não e só comparar o alvo com `nums[mid]`. Também precisa olhar os limites da metade.
Erros comuns
- tratar como busca binaria comum e mover para o lado errado
- esquecer de identificar qual metade esta ordenada antes de decidir
Passo 1 - Entender o que a rotação mudou
Antes da rotação, a busca binaria normal funciona porque o array inteiro esta ordenado.
Depois da rotação, o array inteiro não parece mais ordenado:
[4, 5, 6, 7, 0, 1, 2]
Mas isso não virou bagunca total.
Ainda existem trechos ordenados. O problema agora e descobrir, em cada passo, qual lado continua em ordem.
Passo 2 - Escrever a versão inicial mais direta
A versão inicial e simples:
- percorra o array
- compare cada valor com
target
Funciona.
Mas joga fora a principal pista do problema: a entrada continua quase ordenada.
Passo 3 - Perguntar o que continua verdadeiro
Escolha um mid.
Mesmo com a rotação, uma destas metades vai estar ordenada:
- esquerda:
nums[left]..nums[mid] - direita:
nums[mid]..nums[right]
Se a esquerda estiver ordenada, você decide:
targetesta dentro desse intervalo?- se sim, vai para a esquerda
- se não, vai para a direita
Se a direita estiver ordenada, faz a mesma checagem do outro lado.
Passo 4 - O insight de verdade
A busca binaria tradicional pergunta:
targete maior ou menor quenums[mid]?
Aqui isso não basta.
A pergunta correta vira:
- qual metade esta ordenada?
- o alvo cabe dentro dela?
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function search(nums: number[], target: number): number {
// sua solução aqui
return -1
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(log n)
Espaço: O(1)
Solução 1 - Varredura linear
Boa versão inicial para deixar claro o que esta sendo desperdicado.
export function search(nums: number[], target: number): number {
for (let index = 0; index < nums.length; index += 1) {
if (nums[index] === target) {
return index
}
}
return -1
}Funciona, mas custa O(n) e ignora a estrutura do problema.
Solução 2 - Busca binaria adaptada
Agora você usa a metade ordenada como critério de decisão.
export function search(nums: number[], target: number): number {
let left = 0
let right = nums.length - 1
while (left <= right) {
const mid = Math.floor((left + right) / 2)
if (nums[mid] === target) {
return mid
}
if (nums[left] <= nums[mid]) {
const targetIsOnLeft = nums[left] <= target && target < nums[mid]
if (targetIsOnLeft) {
right = mid - 1
} else {
left = mid + 1
}
} else {
const targetIsOnRight = nums[mid] < target && target <= nums[right]
if (targetIsOnRight) {
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}O ponto central e simples: use a ordem que sobrou para cortar metade do espaco de busca.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial seria varrer tudo em
O(n). A versão forte ainda usabusca binaria, mas antes de decidir o lado eu descubro qual metade esta ordenada. Depois verifico se o alvo cabe nesse intervalo ordenado ou no outro. Assim continuo descartando metade do array por vez.
Isso mostra que você:
- não decorou só o modelo comum
- entendeu o que a rotação muda e o que ela não muda
- usa os limites do intervalo para justificar o corte
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- adaptar
busca binariapara entradas “quase ordenadas” - decidir com base em invariantes locais
- usar a parte ordenada restante em vez de desistir para uma varredura
O ponto não e decorar o caso rotacionado.
O ponto e aprender a procurar a propriedade que ainda sobreviveu ao problema.