Search in Rotated Sorted Array

Q: Qual é a complexidade de tempo da busca em um array ordenado rotacionado?

Tempo O(log n) e espaço extra O(1) . A cada etapa, mantém-se uma metade do intervalo, então 5000 elementos precisam de no máximo 13 etapas. Encontrar primeiro o ponto de rotação também é O(log n) , com cerca do dobro de etapas.

Q: O algoritmo funciona quando o array contém duplicatas?

Não da forma como está escrito. Quando nums[lo] , nums[mid] e nums[hi] são iguais, não é possível provar que nenhuma das metades está ordenada. A solução usual avança lo em uma posição nesse caso, o que mantém a resposta correta, mas faz com que o pior caso seja O(n) .

Q: Você deve encontrar primeiro o ponto de rotação ou pesquisar em uma única passagem?

Ambos são executados em O(log n) . Encontrar o mínimo primeiro divide o problema em duas buscas binárias simples. A busca em uma única passagem faz o trabalho em um único loop com menos etapas, e é a versão que a maioria dos entrevistadores espera.

MédioBusca binária

+10

Uma lista de inteiros distintos foi ordenada em ordem crescente e, em seguida, rotacionada: algum número de elementos, possivelmente zero, foi retirado do início e movido para o final, na mesma ordem. Por exemplo, [2, 5, 8, 11, 15, 19, 23] rotacionada em 4 se torna [15, 19, 23, 2, 5, 8, 11]. Você recebe a lista rotacionada nums e um inteiro target. Retorne o índice de target em nums, contando a partir de 0, ou -1 se ele não estiver lá, em O(log n) tempo.

Função

search(nums: integer-array, target: integer) → integer

numsinteger-array: a lista rotacionada ordenada de números inteiros distintos
targetinteger: o valor a procurar
Retornainteger: o índice de target em nums, ou -1 se ele não estiver presente

Restrições

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i], target ≤ 10⁴
Todos os valores em nums são distintos.
nums é uma lista crescente rotacionada por algum k com 0 ≤ k < nums.length; k = 0 a deixa sem rotação.

Exemplos

Entrada: nums = [15, 19, 23, 2, 5, 8, 11]target = 5
Saída: 4
Explicação: O primeiro meio, índice 3, contém 2, então a metade direita [2, 5, 8, 11] está ordenada e contém 5. O próximo meio, índice 5, contém 8; a parte esquerda ordenada [5, 8] contém 5, o que leva ao índice 4.

Entrada: nums = [40, 50, 60, 70, 10, 20, 30]target = 65
Saída: -1
Explicação: 65 ficaria entre 60 e 70, e nenhum elemento o contém. O primeiro elemento do meio, 70, coloca 65 na parte esquerda ordenada [40, 50, 60, 70], e o intervalo diminui até ficar vazio.

Entrada: nums = [8, 13, 21, 1, 3, 5]target = 13
Saída: 1
Explicação: O primeiro elemento do meio, índice 2, contém 21. A parte esquerda [8, 13, 21] está ordenada e 13 fica entre 8 e 21, então a parte direita é descartada. Em seguida, a busca encontra 13 no índice 1.

Para ir além

Se nums puder conter duplicatas, nenhum algoritmo poderá garantir O(log n). Você consegue provar isso com uma lista rotacionada de 1s que esconde um único 0?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Uma lista ordenada rotacionada consiste em duas sequências ordenadas: [15, 19, 23] e depois [2, 5, 8, 11]. Comparar target com o valor do meio já não indica em qual lado ele está. Mas, independentemente de onde você divida a lista, pelo menos uma das metades está ordenada, e uma comparação indica se target pode estar nessa metade.

Examine cada elemento

Intuição

Verifique cada índice e retorne o primeiro cujo valor seja igual a target, ou -1 após o loop. Ele lê cada elemento, então está correto para qualquer lista. Ele ignora os dois trechos ordenados: 5000 elementos custam até 5000 comparações, enquanto uma busca binária precisa de 13.

Algoritmo

Para cada índice i de 0 a n-1, compare nums[i] com target.
Se forem iguais, retorne i.
Após o loop, retorne -1.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

Encontre o ponto de rotação e, em seguida, faça uma busca binária

Intuição

O segundo trecho começa no menor valor; chame seu índice de k. Tanto nums[k..n-1] quanto nums[0..k-1] estão ordenados, e todos os valores do primeiro trecho são maiores que todos os valores do segundo. Depois de descobrir k, comparar target com nums[k] e nums[n-1] determina em qual trecho procurar, e uma busca binária comum conclui a tarefa.

Para encontrar k, compare o valor do meio com nums[hi]. Se nums[mid] > nums[hi], os valores diminuem em algum ponto depois de mid, então o mínimo está à direita. Caso contrário, nums[mid..hi] cresce sem diminuir, então o mínimo está em mid ou antes dele. No primeiro exemplo, os valores centrais são 2, 19 e 23, resultando em k = 3, e 5 está entre nums[3] = 2 e nums[6] = 11. Duas buscas binárias custam cerca de 2 log2 n etapas.

Algoritmo

Defina lo = 0 e hi = n-1. Enquanto lo < hi, calcule mid; se nums[mid] > nums[hi], defina lo = mid + 1; caso contrário, defina hi = mid.
O índice final k contém o menor valor.
Se nums[k] ≤ target ≤ nums[n-1], faça uma busca binária nos índices de k a n-1; caso contrário, pesquise de 0 a k-1.
Retorne o índice encontrado ou -1 se o intervalo ficar vazio.

def search(nums, target):
    n = len(nums)
    # 1. Find k, the index of the smallest value, where the second run starts.
    lo, hi = 0, n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the drop is right of mid
        else:
            hi = mid      # mid is in the low run: the minimum is at mid or left of it
    k = lo
    # 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
    if nums[k] <= target <= nums[n - 1]:
        lo, hi = k, n - 1
    else:
        lo, hi = 0, k - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Uma busca binária na metade ordenada

Intuição

Mantenha a promessa da busca binária: se target estiver na lista, seu índice estará entre lo e hi. Os valores caem apenas uma vez em toda a lista, então, no máximo, uma das duas metades ao redor de mid contém a queda, e a outra está ordenada. Se nums[lo] ≤ nums[mid], a metade esquerda está ordenada; caso contrário, a direita está.

Para a metade ordenada, um teste do intervalo em suas duas extremidades indica se target pode estar dentro dela, por exemplo, nums[lo] ≤ target < nums[mid] na esquerda. Se puder, pesquise nessa metade; se não, target só pode estar na outra metade. A cada etapa, o intervalo é reduzido pela metade: no máximo 13 etapas para 5000 elementos.

Algoritmo

Defina lo = 0 e hi = n-1.
Enquanto lo ≤ hi, calcule mid e retorne-o se nums[mid] for igual a target.
Se nums[lo] ≤ nums[mid], a metade esquerda está ordenada: defina hi = mid - 1 quando nums[lo] ≤ target < nums[mid]; caso contrário, defina lo = mid + 1.
Caso contrário, a metade direita está ordenada: defina lo = mid + 1 quando nums[mid] < target ≤ nums[hi]; caso contrário, defina hi = mid - 1.
Quando o loop terminar, retorne -1.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            # nums[lo..mid] is sorted: target is in it only if it fits its range
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # nums[mid..hi] is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Armadilhas e casos extremos

Escrever nums[lo] < nums[mid] em vez de ≤. Quando restam dois elementos, mid é igual a lo, e o teste estrito considera [9, 4] uma metade direita ordenada: target = 4 retorna -1.
Comparar target com nums[mid] primeiro. No primeiro exemplo, com target = 19, o valor do meio, 2, é menor, então a busca avança para a direita e não encontra o índice 1.
Testar apenas uma extremidade da metade ordenada. Em [40, 50, 60, 70, 80, 10, 20], com target = 80, usar apenas target ≥ nums[lo] direciona a busca para [40, 50, 60, 70].
Em Rust, k - 1 em um usize causa underflow quando k = 0, a lista não rotacionada. Use intervalos semiabertos.
Em Lua e R, retornar a posição baseada em 1. Subtraia 1.

Perguntas frequentes3

Qual é a complexidade de tempo da busca em um array ordenado rotacionado?

Tempo O(log n) e espaço extra O(1). A cada etapa, mantém-se uma metade do intervalo, então 5000 elementos precisam de no máximo 13 etapas. Encontrar primeiro o ponto de rotação também é O(log n), com cerca do dobro de etapas.

O algoritmo funciona quando o array contém duplicatas?

Não da forma como está escrito. Quando nums[lo], nums[mid] e nums[hi] são iguais, não é possível provar que nenhuma das metades está ordenada. A solução usual avança lo em uma posição nesse caso, o que mantém a resposta correta, mas faz com que o pior caso seja O(n).

Você deve encontrar primeiro o ponto de rotação ou pesquisar em uma única passagem?

Ambos são executados em O(log n). Encontrar o mínimo primeiro divide o problema em duas buscas binárias simples. A busca em uma única passagem faz o trabalho em um único loop com menos etapas, e é a versão que a maioria dos entrevistadores espera.

def search(nums, target):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

nums = [15, 19, 23, 2, 5, 8, 11]
target = 5

Saída Esperada

Search in Rotated Sorted Array

Função

Restrições

Exemplos

Dicas

Solução

Examine cada elemento

Encontre o ponto de rotação e, em seguida, faça uma busca binária

Uma busca binária na metade ordenada

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos