Ricerca binaria su array ruotati e non ordinati

Un array ordinato ruotato è un array ordinato che è stato tagliato in corrispondenza di un pivot e le cui due parti sono state scambiate. Ad esempio, [4, 5, 6, 7, 0, 1, 2] è l'array ordinato [0,1,2,4,5,6,7] ruotato all'indice 4. La ricerca binaria standard non funziona in questo caso perché l'array non è più ordinato globalmente.

L'idea fondamentale è che almeno una metà dell'array è sempre ordinata dopo una qualsiasi rotazione. La ricerca binaria deve identificare quale metà è ordinata prima di decidere come spostare i limiti.

Dopo aver calcolato mid, confronti arr[lo] con arr[mid]. Se arr[lo] <= arr[mid], la metà sinistra è ordinata; altrimenti è ordinata la metà destra. Una volta stabilito quale metà è ordinata, può verificare se il target rientra in quell'intervallo ordinato e restringere di conseguenza la ricerca.

Questo albero decisionale consente di scartare esattamente metà dell'array a ogni passaggio, mantenendo la complessità O(log n) anche con un array ruotato.

Seguiamo passo per passo search_rotated([4,5,6,7,0,1,2], 0). Inizialmente lo=0, hi=6, mid=3, arr[mid]=7. Il target 0 si trova nella metà sinistra ordinata [4..7]? No, quindi impostiamo lo=4. Ora lo=4, hi=6, mid=5, arr[mid]=1. La metà sinistra [0,1] è ordinata (arr[lo]=0 <= arr[mid]=1). 0 si trova in [0..1)? Sì, quindi impostiamo hi=4. Ora lo=4, hi=4, mid=4, arr[4]=0: trovato all'indice 4.

Quando l'array ordinato ruotato può contenere duplicati, ad esempio [1,3,1,1,1], la condizione nums[lo] == nums[mid] è ambigua: non è possibile stabilire quale metà sia ordinata. La soluzione sicura consiste nell'incrementare lo (oppure decrementare hi) di uno e riprovare. Nel caso peggiore, il tempo passa a O(n); è opportuno menzionarlo al selezionatore.

Un problema correlato consiste nel trovare il minimo in un array ordinato ruotato senza cercare uno specifico target. Il minimo si trova sempre nella metà non ordinata. A ogni passaggio: se arr[mid] > arr[hi], il minimo si trova nella metà destra (lo = mid + 1); altrimenti si trova nella metà sinistra, includendo mid (hi = mid). Quando lo == hi, il minimo è stato trovato.

La condizione arr[lo] <= arr[mid] funziona perché, in un segmento ordinato (o ordinato senza rotazione), il primo elemento è sempre il più piccolo. Se arr[lo] <= arr[mid], all'interno di [lo..mid] non si è verificata alcuna rotazione, quindi quella metà è ordinata. L'uguaglianza gestisce il caso in cui lo == mid: un segmento di un solo elemento è ovviamente ordinato.

Al contrario, se arr[lo] > arr[mid], il pivot della rotazione deve trovarsi tra lo e mid; ciò significa che la metà destra [mid..hi] è il segmento ordinato contiguo.

La ricerca in un array ordinato ruotato con la ricerca binaria mantiene un tempo O(log n) e uno spazio O(1), perché a ogni iterazione dimezziamo comunque lo spazio di ricerca. L'unica differenza rispetto alla ricerca binaria classica è un controllo aggiuntivo a tempo costante per identificare quale metà è ordinata.

Con i duplicati, nel caso peggiore la complessità passa a O(n), perché potremmo incrementare lo di una sola posizione a ogni passaggio. Espliciti questo compromesso: dimostra che tiene conto dei casi limite oltre al normale percorso di esecuzione.

LeetCode 33 'Search in Rotated Sorted Array' è la forma canonica di questo problema. I vincoli garantiscono l'assenza di duplicati e un'unica rotazione. La soluzione è la funzione search_rotated che abbiamo scritto in precedenza. Punti chiave per il colloquio: dichiari sempre l'ipotesi di assenza di duplicati, verifichi le disuguaglianze con un esempio concreto sul confine e confermi che l'indice restituito sia corretto sia nei casi in cui l'elemento viene trovato sia in quelli in cui non viene trovato.

LeetCode 153 'Find Minimum in Rotated Sorted Array' chiede di trovare il minimo in assenza di duplicati. L'approccio consiste nel confrontare arr[mid] con arr[hi], non con arr[lo], per determinare da quale lato si trovi il minimo. Se arr[mid] > arr[hi], il minimo si trova a destra; altrimenti si trova in mid o a sinistra. Il procedimento converge al minimo in O(log n).

Una volta in grado di trovare l'elemento minimo, conosce anche il numero di rotazioni: l'indice del minimo corrisponde esattamente al numero di posizioni verso destra di cui è stato ruotato l'array. Ad esempio, in [4,5,6,7,0,1,2] il minimo si trova all'indice 4, quindi l'array è stato ruotato di 4 posizioni.

Conoscere il pivot consente di applicare la ricerca binaria standard trattando gli indici modulo n: real_idx = (mid + pivot) % n. Questa formulazione alternativa può semplificare il ragionamento quando si lavora con strutture indicizzate circolarmente.

Quando si trova davanti a un problema sugli array ruotati durante un colloquio, segua questo albero decisionale. Per prima cosa stabilisca se deve trovare un target oppure trovare il minimo. Per trovare un target, utilizzi l'approccio basato sull'identificazione della metà ordinata. Per trovare il minimo, confronti mid con hi. Se sono possibili duplicati, menzioni il caso peggiore O(n) e aggiunga il fallback che restringe i confini.

Si eserciti tracciando il codice sui tre esempi classici: nessuna rotazione, una rotazione e una rotazione che porta il minimo all'ultima posizione.

In questa lezione ha imparato che: un array ordinato ruotato contiene sempre almeno una metà ordinata, occorre confrontare arr[lo] con arr[mid] per identificare la metà ordinata prima di decidere dove cercare e per trovare il minimo si confrontano arr[mid] e arr[hi] così da individuare il pivot della rotazione. Nel prossimo argomento esploreremo le varianti della ricerca binaria lower bound e upper bound.