Find First and Last Position of Element in Sorted Array

Q: Qual è la complessità temporale per trovare la prima e l'ultima posizione?

Tempo O(log n) e spazio O(1) , con due ricerche binarie. Nessuna delle due si ferma quando trova una corrispondenza, quindi il costo non dipende da quante copie del valore cercato ci sono: circa 14 passaggi per ricerca per 10^4 valori.

Q: Che cos'è un limite inferiore nella ricerca binaria?

Il limite inferiore di un valore è il primo indice il cui elemento è almeno pari a quel valore, oppure la lunghezza della lista se non ce n’è nessuno. È il punto in cui il valore verrebbe inserito per mantenere la lista ordinata. Il limite superiore è il primo indice il cui elemento è strettamente maggiore.

Q: Una funzione di ricerca binaria può trovare sia il primo che l’ultimo indice?

Sì. Aggiungi un flag alla ricerca: quando trovi una corrispondenza, registra l’indice e continua a cercare a sinistra per trovare la prima occorrenza, o a destra per trovare l’ultima. Funziona anche chiamare una ricerca per limite inferiore su target e su target + 1 . Entrambe hanno complessità O(log n) .

MedioRicerca binaria

+10

Ricevi un elenco di numeri interi nums ordinati in ordine non decrescente, quindi un valore può ripetersi, e un numero intero target. Restituisci un elenco di due indici, contando da 0: la prima e l’ultima posizione in cui compare target. Se target non è nell’elenco, restituisci [-1, -1]. Punta a un tempo O(log n).

Funzione

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

numsinteger-array: l'elenco ordinato di numeri interi, che può contenere valori ripetuti
targetinteger: il valore da cercare
Restituisceinteger-array: il primo e l’ultimo indice di target, oppure [-1, -1] se è assente

Vincoli

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
nums è ordinato in ordine non decrescente.

Esempi

Input: nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
Output: [1, 3]
Spiegazione: Le tre copie di 5 si trovano agli indici 1, 2 e 3, quindi la serie inizia a 1 e termina a 3. L'indice 0 contiene 3 e l'indice 4 contiene 8, quindi la serie non può estendersi oltre.

Input: nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
Output: [-1, -1]
Spiegazione: 7 si troverebbe tra 5 all’indice 3 e 8 all’indice 4, e nessuno dei due è 7. La lista non contiene alcuna copia, quindi la risposta è [-1, -1].

Per approfondire

Se la stessa lista riceve migliaia di query per obiettivi diversi, una sola scansione preventiva può rendere ogni query più veloce di O(log n)?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Una ricerca binaria semplice si ferma alla copia di target che incontra, e quella copia può trovarsi in qualsiasi punto della sequenza. Cerca invece un limite inferiore: il primo indice il cui valore è almeno pari a un dato numero. I limiti inferiori di target e target + 1 forniscono entrambi gli estremi della sequenza in O(log n).

Esamina l’intero elenco

Intuizione

Percorri l’elenco una volta. Il primo indice che contiene target è l’inizio e l’ultimo è la fine. Se target non compare mai, entrambi rimangono -1.

Funziona con qualsiasi elenco, ordinato o meno, e questo è il suo punto debole: legge tutti i valori n. Un elenco di 10^4 valori richiede 10.000 confronti, mentre ne basterebbero circa 28.

Algoritmo

Imposta first = last = -1.
Per ogni indice i, se nums[i] è uguale a target, imposta first = i quando first è ancora -1, e imposta last = i.
Restituisci [first, last].

def searchRange(nums, target):
    first = last = -1
    for i, value in enumerate(nums):
        if value == target:
            if first == -1:
                first = i  # the first match fixes the start
            last = i  # every later match moves the end
    return [first, last]

Trova una copia, poi espandi

Intuizione

Esegui una ricerca binaria per trovare un indice qualsiasi che contenga target. La lista è ordinata, quindi tutte le copie si trovano in un’unica sequenza ininterrotta attorno a quell’indice: spostati a sinistra e a destra finché il vicino è ancora target.

La ricerca ha costo O(log n) e l’attraversamento richiede un passaggio per copia, k in totale. Quando la maggior parte della lista è composta da target, diciamo 10^4 copie, l’attraversamento legge ogni valore e si torna a una scansione lineare.

Algoritmo

Esegui una ricerca binaria per trovare un indice qualsiasi found per cui nums[found] == target.
Se non ce n'è nessuno, restituisci [-1, -1].
Sposta first a sinistra da found finché il valore precedente è uguale a target.
Sposta last a destra da found finché il valore successivo è uguale a target.
Restituisci [first, last].

def searchRange(nums, target):
    # An ordinary binary search finds some copy of target, if there is one.
    lo, hi = 0, len(nums) - 1
    found = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            found = mid
            break
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    if found == -1:
        return [-1, -1]
    # The copies sit next to each other, so walk out to both ends of the run.
    first = last = found
    while first > 0 and nums[first - 1] == target:
        first -= 1
    while last < len(nums) - 1 and nums[last + 1] == target:
        last += 1
    return [first, last]

Due ricerche binarie del limite inferiore

Intuizione

Poni una domanda diversa: qual è il primo indice il cui valore è almeno value? Quell’indice è il limite inferiore, oppure n se nessun valore soddisfa il criterio. Mantieni un intervallo semiaperto [lo, hi) che lo contenga sempre. Se nums[mid] < value, allora mid e tutti gli elementi precedenti sono troppo piccoli. Altrimenti mid soddisfa il criterio, ma potrebbe soddisfarlo anche un indice precedente, quindi mid resta nell’intervallo come nuovo hi. Il ciclo non si interrompe mai in anticipo quando trova una corrispondenza.

Il limite inferiore di target è il punto in cui inizia la sua sequenza. I valori sono interi, quindi il primo valore maggiore di target si trova al limite inferiore di target + 1 e la sequenza termina un indice prima. Nel primo esempio, il limite inferiore di 5 è 1 e quello di 6 è 4, dove si trova 8: la sequenza è [1, 3]. Le due ricerche richiedono circa 28 passaggi per 10^4 valori, indipendentemente dalla lunghezza della sequenza.

Algoritmo

Scrivi lowerBound(value): inizia con lo = 0, hi = n; mentre lo < hi, se nums[mid] < value imposta lo = mid + 1, altrimenti imposta hi = mid; restituisci lo.
Imposta first = lowerBound(target).
Se first == n oppure nums[first] != target, restituisci [-1, -1].
Imposta last = lowerBound(target + 1) - 1 e restituisci [first, last].

def lowerBound(nums, value):
    # The first index whose number is at least value, or len(nums) if none is.
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < value:
            lo = mid + 1  # nums[mid] and everything before it is too small
        else:
            hi = mid  # nums[mid] qualifies, but an earlier index might too
    return lo


def searchRange(nums, target):
    first = lowerBound(nums, target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    # The run of target ends right before the first number above target.
    last = lowerBound(nums, target + 1) - 1
    return [first, last]

Trappole e casi limite

Restituire immediatamente non appena nums[mid] == target. Quell'indice può trovarsi in qualsiasi punto della sequenza: in [3, 5, 5, 5, 8] il primo elemento centrale è all'indice 2, che non è nessuno dei due estremi.
Scrivere hi = mid - 1 nella ricerca del limite inferiore quando nums[mid] ≥ value. Così si scarta mid, che potrebbe essere la risposta.
Leggere nums[first] senza verificare first < n. Quando target è maggiore di tutti i valori, come 13 negli esempi, il limite inferiore è n, cioè una posizione oltre la fine.
Dimenticare lo spostamento in Lua e R. Le loro liste iniziano da 1, quindi sottrai 1 da entrambe le posizioni.

Domande frequenti3

Qual è la complessità temporale per trovare la prima e l'ultima posizione?

Tempo O(log n) e spazio O(1), con due ricerche binarie. Nessuna delle due si ferma quando trova una corrispondenza, quindi il costo non dipende da quante copie del valore cercato ci sono: circa 14 passaggi per ricerca per 10^4 valori.

Che cos'è un limite inferiore nella ricerca binaria?

Il limite inferiore di un valore è il primo indice il cui elemento è almeno pari a quel valore, oppure la lunghezza della lista se non ce n’è nessuno. È il punto in cui il valore verrebbe inserito per mantenere la lista ordinata. Il limite superiore è il primo indice il cui elemento è strettamente maggiore.

Una funzione di ricerca binaria può trovare sia il primo che l’ultimo indice?

Sì. Aggiungi un flag alla ricerca: quando trovi una corrispondenza, registra l’indice e continua a cercare a sinistra per trovare la prima occorrenza, o a destra per trovare l’ultima. Funziona anche chiamare una ricerca per limite inferiore su target e su target + 1. Entrambe hanno complessità O(log n).

def searchRange(nums, target):
    # Scrivi il codice qui

Test #1

Test #2

Argomenti

nums = [3, 5, 5, 5, 8, 9, 9, 12]
target = 5

Output atteso

[1, 3]

Find First and Last Position of Element in Sorted Array

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Esamina l’intero elenco

Trova una copia, poi espandi

Due ricerche binarie del limite inferiore

Trappole e casi limite

Domande frequenti3

Problemi simili