#Ricerca binariaLa ricerca binaria1, in inglese binary search, è una tecnica di ricerca che spesso permette di velocizzare una ricerca lineare.
Per capire l’idea alla base consideriamo il seguente esempio: un nostro amico sta pensando a un numero 𝑁 da 1 a 100 e noi dobbiamo indovinarlo. Le domande che possiamo fare sono del tipo “Il numero 𝑁 è minore o uguale a X?”.
La prima domanda che chiunque farebbe è “Il numero è minore o uguale a 50?” perché, qualsiasi sia la risposta, avremo scartato metà delle opzioni. Proseguendo con un ragionamento simile, con ogni domanda possiamo dimezzare lo spazio di ricerca.
Quante domande ci serviranno per determinare il numero? Ovvero, quante volte dobbiamo dimezzare lo spazio di ricerca per arrivare a un solo numero plausibile e quindi alla soluzione?
Per rispondere è più facile capovolgere il problema chiedendosi quante volte, partendo da un singolo elemento, si debba raddoppiare lo spazio di ricerca per ottenere la dimensione iniziale.
Se 𝑄 è il numero di query2 e 𝐷 la dimensione dello spazio di ricerca, vale 2𝑄=𝐷, da cui
𝑄=log2𝐷
Si ricorda che un cambio di base nei logaritmi equivale a un fattore moltiplicativo costante, quindi è lecito omettere la base e affermare che la ricerca binaria impiega 𝒪︀(log𝐷) query, dove 𝐷 è la dimensione dello spazio di ricerca.
Una possibile implementazione del problema sopra descritto è la seguente:
int N = 42, queries;
bool chiedi(int X) {
return N <= X;
}
int main() {
queries = 0;
int left = 1, right = 100;
while (left != right) {
queries++;
int mid = (left + right) / 2;
if (chiedi(mid))
right = mid;
else
left = mid + 1;
}
if (left == N)
cout << "Correct: " << queries << " queries" << endl;
}
È bene spendere qualche parola su alcuni dettagli dell’implementazione.
Con left e right indichiamo gli estremi (inclusi) dello spazio di ricerca, che dunque conterrà right− left+1 elementi. Vogliamo reiterare l’algoritmo finché abbiamo più di un elemento tra i candidati, cioè finché right è diverso da left.
A ogni passo della ricerca si fa una query nel punto medio dell’intervallo per capire in quale delle due metà proseguire la ricerca.
È possibile anche implementare la ricerca binaria ricorsivamente:
int ricerca_binaria(int left, int right) {
if (left == right) return left;
int mid = (left + right) / 2;
if (chiedi(mid))
return ricerca_binaria(left, mid);
else
return ricerca_binaria(mid + 1, right);
}
int main() {
cout << ricerca_binaria(1, 100) << endl;
}
Un’applicazione comune di questo algoritmo è nella ricerca di un elemento all’interno di un vettore ordinato.
vector<int> A = {1, 2, 3, 5, 6, 9, 11, 24};
int left = 0, right = A.size() - 1;
int cercato = 9;
while (left != right) {
int mid = (left + right) / 2;
if (A[mid] >= cercato) {
right = mid;
} else {
left = mid + 1;
}
}
if (A[left] == cercato) {
cout << "L'elemento è presente!" << endl;
cout << "Posizione: " << left << endl;
}
In questo caso, dal momento che il vettore è ordinato, invece di scorrere tutto l’array per verificare se sia presente o meno il valore cercato in 𝒪︀(𝑁), possiamo fare una ricerca binaria:
Guardo l’elemento al centro dell’intervallo in cui sto cercando e, se questo è maggiore o uguale, proseguo la ricerca nella metà sinistra, altrimenti nella metà destra. La complessità è 𝒪︀(log𝑁).
Vediamo un’illustrazione passo dopo passo per comprendere meglio come funziona la ricerca binaria per trovare un elemento in un array. Cerchiamo ad esempio l’elemento 9, come nell’esempio sopra.
0
1
2
3
4
5
6
7
1
2
3
5
6
9
11
24
𝑙
𝑟
Passo 1: all’inizio lo spazio di ricerca è da 0 a 7.
0
1
2
3
4
5
6
7
1
2
3
5
6
9
11
24
𝑙
𝑚
𝑟
Passo 2: guardiamo al centro: 𝐴[𝑚]=5<9, quindi se c’è 9 è a destra di 𝑚. Impostiamo 𝑙←𝑚+1.
0
1
2
3
4
5
6
7
1
2
3
5
6
9
11
24
𝑙
𝑟
Passo 3: ora lo spazio di ricerca è da 4 a 7.
0
1
2
3
4
5
6
7
1
2
3
5
6
9
11
24
𝑙
𝑚
𝑟
Passo 4: 𝐴[𝑚]=9≥9 quindi 𝑟←𝑚.
0
1
2
3
4
5
6
7
1
2
3
5
6
9
11
24
𝑙, 𝑚
𝑟
Passo 5: 𝐴[𝑚]=6<9 quindi 𝑙←𝑚+1.
0
1
2
3
4
5
6
7
1
2
3
5
6
9
11
24
𝑙, 𝑟
Passo 6: 𝑙=𝑟 dunque l’algoritmo termina.
Per verificare solamente se in un vettore sia presente un valore si può usare std::binary_search(), mentre per determinarne la posizione si usa std::lower_bound(). Entrambe queste funzioni hanno complessità 𝒪︀(log𝑁).
vector<int> A = {1, 2, 3, 5, 6, 9, 11, 24};
int cercato = 11;
if (binary_search(A.begin(), A.end(), cercato)) {
cout << "Elemento presente" << endl;
int pos = lower_bound(A.begin(), A.end(), cercato) - A.begin();
cout << "Posizione: " << pos << endl;
} else {
cout << "Elemento non presente" << endl;
}
In generale, la ricerca binaria si può applicare quando i valori rispettano un qualche ordinamento che ci permette di separare in due metà lo spazio di ricerca sapendo in quale delle due metà si potrebbe trovare.
Un esempio classico è l’albero binario di ricerca, struttura dati in cui ogni nodo contiene un valore e tutti i valori nel sottoalbero sinistro sono minori mentre quelli nel sottoalbero destro sono più grandi.
#Ricerca binaria sulla rispostaUn’applicazione non banale della ricerca binaria è dare la risposta a un problema di minimo o di massimo. Consideriamo il seguente problema.
Factory Machines CSES
Possediamo 𝑁 macchinari e il macchinario 𝑖 impiega 𝑆𝑖 secondi a produrre un oggetto. Vogliamo produrre in totale 𝐾 oggetti. Qual è il tempo minimo necessario?
Prova il problema online: https://cses.fi/problemset/task/1620
Soluzione
Proviamo a risolvere un problema più facile: in un tempo 𝑡 quanti oggetti posso produrre? È facile vedere che ogni macchinario può produrre ⌊𝑡𝑆𝑖⌋ oggetti, dunque in totale ne possiamo produrre ∑𝑁−1𝑖=0⌊𝑡𝑆𝑖⌋.
Per comodità diciamo 𝑓(𝑡)=∑𝑁−1𝑖=0⌊𝑡𝑆𝑖⌋.
ll f(ll t) {
ll sum = 0;
for (ll s : S) {
sum += t / s;
if (sum > 1e9)
return sum;
}
return sum;
}
A questo punto potremmo provare tutti i 𝑡 da 0 in poi e fermarci quando il numero di oggetti che si possono produrre è almeno 𝐾. Notiamo però che, se 𝑇 è il tempo minimo necessario per produrre 𝐾 oggetti, per tutti i tempi 𝑡<𝑇 potremo produrre meno di 𝐾 oggetti, mentre per tutti i 𝑡≥𝑇 ne produrremo almeno 𝐾.
Dato che per i nostri scopi il numero di oggetti potrebbe diventare molto grande, restituiamo la somma appena supera il valore di 𝐾. Ricordiamoci di iniziare la ricerca con un valore del limite destro 𝑟 sufficientemente grande, da scegliere opportunamente in base al problema.
Date queste premesse, è possibile fare una ricerca binaria sul punto in cui 𝑓(𝑡) diventa maggiore o uguale a 𝐾.
ll l = 0, r = 1e18;
while (r != l) {
ll m = (r + l) / 2;
if (f(m) < K)
l = m + 1;
else
r = m;
}
cout << l << '\n';
La complessità finale della soluzione passa da 𝒪︀(𝑁𝑇) a 𝒪︀(𝑁log𝑇).
In alcuni problemi, la funzione su cui facciamo ricerca binaria può diventare molto complessa, come nell’esempio che segue. La condizione che ci permette di fare ricerca binaria su una funzione è che questa sia monotona (non decrescente o non crescente) nell’intervallo di interesse.
Christmas lights OIS2022-23
Abbiamo una fila di 𝑁 luci colorate di 𝐶 colori diversi; il colore della luce 𝑖-esima è 𝐴𝑖 (0≤𝐴𝑖<𝐶≤ 𝑁). Quanto è lungo il più corto sottoarray che contiene tutti i colori?
Prova il problema online: https://training.olinfo.it/task/ois_lights
Soluzione
Assumiamo che la risposta sia 𝐿. Possiamo osservare due cose:
•Tutti i sottoarray più corti di 𝐿 non contengono 𝐶 colori distinti, altrimenti la risposta non sarebbe 𝐿;•Per ogni lunghezza 𝐾 con 𝐿≤𝐾≤𝑁 esiste almeno un sottoarray che contiene tutti i colori. Basta considerare il sottoarray lungo 𝐿 che li contiene tutti e espanderlo agli estremi finché non è lungo 𝐾.Controllare se esista un sottoarray di lunghezza ℓ contenente tutti i colori richiede tempo 𝒪︀(𝑁) nel seguente modo:
bool controlla(int l) {
vector<int> conta(C);
int colori_mancanti = C;
for (int i = 0; i < l; i++) {
conta[A[i]]++;
if (conta[A[i]] == 1) colori_mancanti--;
}
if (colori_mancanti == 0) return true;
for (int i = l; i < N; i++) {
conta[A[i - l]]--;
if (conta[A[i - l]] == 0) colori_mancanti++;
conta[A[i]]++;
if (conta[A[i]] == 1) colori_mancanti--;
if (colori_mancanti == 0) return true;
}
return false;
}
La funzione controlla(int l) restituisce true solo se esiste un sottoarray di lunghezza ℓ che contiene tutti i colori.
Una soluzione quadratica potrebbe controllare tutti gli ℓ da 𝐶 a 𝑁 e stampare il valore minimo per cui controlla(l) restituisce true.
Tuttavia, per le osservazioni fatte in precedenza, vediamo che per un prefisso di valori fino a 𝐿, controlla(l) restituisce false, mentre per il restante suffisso restituisce true e quindi possiamo fare ricerca binaria su questo punto.
Sappiamo che si trova tra 𝐶 e 𝑁, quindi proviamo a metà. Se otteniamo true dobbiamo controllare nella metà sinistra, altrimenti controlliamo nella metà destra.
int left = C, right = N;
while (left != right) {
int mid = (left + right) / 2;
if (controlla(mid))
right = mid;
else
left = mid + 1;
}
cout << left << endl;
Quando ci viene richiesto di trovare il massimo o il minimo valore per il quale vale una certa proprietà e questa proprietà vale solo per un prefisso o solo per un suffisso, allora è solitamente possibile fare una ricerca binaria sul punto in cui cambia la risposta.
#Problemi consigliati
Factory Machines (https://cses.fi/problemset/task/1620)
Filiali bilanciate (https://training.olinfo.it/task/ois_filiali)
Array Division (https://cses.fi/alon/task/1085)
Multiplication Table (https://cses.fi/problemset/task/2422)
1talvolta chiamata anche ricerca dicotomica2Domande.