Note
Per chi non sappia ancora cosa e’ una binary search, puo’ saltare direttametne a dopo la Preface, ma sarebbe meglio se si guarda prima la binary seacrh da qualche parte per farsi un idea.
Chiamo lb il lower bound, ub l’upper bound e m \lfloor \frac{lb+ub}{2} \rfloor.
Preface
Vedo spesso gente che si confonde nell’implementare la ricerca binaria: non capisce se mettere lb<=ub, lb<ub, lb<ub-1, ... o se mettere m=ub, m=lb, m=ub-1, m=lb+1, ... o magari non sa a che valori inizializzare lb e ub.
Questo mi sorprende molto in quanto la ricerca binaria e’ facilmente implementabile allo stesso modo per qualsiasi problema.
Il problema che la binary search risolve
Prima di tutto definiamo il problema risolto dalla binary search:
data una funzione f: \mathbb{Z} \rightarrow \{0,1\} crescente: trova il punto dove la funzione passa da 0 a 1, o meglio, dove si trova l’ultimo 0 (per il primo 1, non cambia ne il problema ne l’algoritmo), sapendo che si trova in [a,b).
Ripeto in modo meno formale: dato un array potenzialmente grande della forma ...,0,0,0,0,1,1,1,1,..., trova dove passa da 0 a 1.
Esempio di formulazione
Potreste aver visto problemi in cui a un primo sguardo pensate di star facendo qualcosa di diverso.
Ad esempio avete un array v lungo n decrescente e volete trovare il primo numero \le k se esiste.
Ma se ci fate caso, con una funzione del tipo
f(x) =
0 se x<0
1 se x \ge n
v_x \le k altrimenti
allora il primo 1 nella funzione sara’ la risposta, con a=0, b=n (in questo modo il primo 1 puo essere in posizione b=n, che vuol dire che non ci sono elementi \le k nell’array).
E’ ache facile notare che questa funzione e’ nella forma (prima 0 poi 1) che ci aspettiamo.
L’implementazione
Essendo il problema risolto cosi definito e’ facile capire che c’e’ poco da confondersi implementando una binary seacrh.
Ecco l’implementazione in pseudocodice:
lb=a;
ub=b;
while(lb<ub-1) {
m=(lb+ub)/2;
if(f(m) == 1) {
ub=m;
} else {
lb=m;
}
}
// lb = posizione dell'ultimo 0
// ub = posizione del primo 1
Queta implementazione di binary search funziona sempre con le assunzioni fatte sopra.
Ovviamente dovete comunque pensare a cosa usare come f e dove sono a e b ma in genere non mi sembra molto complicato.
Non ho esplicitamente messo le dichiarazioni delle variabili, ma in genere dichiarerei m dentro.
Ho messo in questo caso f(m) per genarlita’ ma ovviamente potete mettere una qualsiasi espressione, non c’e’ bisogno che implementiate f come una funzione nel programma.
Nel caso lb+ub possa andare in overflow potete usare m=lb+(ub-lb)/2 per evitare overflow (o std::midpoint, o un tipo piu grande).
Notate che f puo’ essere una funzione anche costosa, non e’ per forza un array gia calcolato.
La binary search ci permette di trovare un punto in sole \lfloor \log_2(b-a+1) \rfloor chiamate a f.
a e b sono generalmente semplici da scegliere se pensate a dove spazia la soluzione,
basta mettere a in modo che f(a)=0 e b in modo che f(b)=1;
eg: se il lb e’ la soluzione al vostro problema e la soluzione e’ in [0,n), allora basta mettere a=0 e b=n, ma se per esempio la soluzione puo non esistere, basta mettere a=-1.
Bonus: ternary search
Prendiamo in considerazione questo problema:
Dato un array v strettamente decrescente fino a v_k e strettamente crescente dopo, trova k (la posizione dell’elemento minimo).
Definiamo f(x) =
0 se x=0
v_x > v_{x-1} altrimenti
k sara’ la posizione dell’ultimo 0 in f, quindi possiamo usare binary search per risolvere il problema (con a=0 e b=n).