Binäärihaku on algoritmi, jolla voi löytää tietyn alkion $n$ alkion järjestetystä taulukosta ajassa $O(\log n)$. Tutustumme seuraavaksi binäärihaun toteuttamiseen sekä sen soveltamiseen algoritmiikassa.

Haun toteutus

Mukava tapa toteuttaa binäärihaku on aloittaa taulukon alusta ja kulkea sitä eteenpäin hyppäyksin. Hypyn pituus on ensin $n$, sitten $n/2$, sitten $n/4$, jne., kunnes lopuksi pituus on $1$. Jokaisen pituuden kohdalla hypitään eteenpäin, kunnes seuraava hyppy veisi taulukon ulkopuolelle tai alkioon, joka on liian suuri.

Seuraava esimerkki etsii alkion $x$ sijainnin järjestetyssä taulukossa $t$, jossa on $n$ alkiota:

int k = 0;
for (int b = n; b >= 1; b /= 2) {
    while (k+b < n && t[k+b] <= x) k += b;
}
if (t[k] == x) // alkio löytyi

Muuttuja $k$ ilmaisee kohdan taulukossa, ja se on aluksi $0$. Muuttuja $b$ määrittää hypyn pituuden. Jos taulukossa on alkio $x$, sen kohta on lopuksi muuttujassa $k$.

Algoritmi vie aikaa $O(\log n)$, koska hypyn pituuksia on yhteensä $O(\log n)$ ja jokaisen pituuden kohdalla while-silmukkaa suoritetaan enintään kaksi kierrosta.

Toistuvat alkiot

Äskeisessä binäärihaun toteutuksessa on etuna, että sitä on helppoa muokata eri tilanteisiin sopivaksi. Esimerkiksi seuraava koodi laskee, montako kertaa järjestetyssä taulukossa esiintyy alkio $x$:

int k1 = -1, k2 = -1;
for (int b = n; b >= 1; b /= 2) {
    while (k1+b < n && t[k1+b] < x) k1 += b;
    while (k2+b < n && t[k2+b] <= x) k2 += b;
}
c = k2-k1; // toistuvien alkioiden määrä

Tässä ideana on, että muuttujaan $k_1$ etsitään viimeinen kohta, jossa taulukon alkio on alle $x$, ja muuttujaan $k_2$ etsitään viimeinen kohta, jossa taulukon alkio on enintään $x$. Niinpä $c=k_2-k_1$ on alkion $x$ toistokertojen määrä taulukossa.

Muutoskohdan etsiminen

Binäärihaun pääasiallinen käyttötarkoitus algoritmiikassa ei ole alkioiden etsiminen taulukosta vaan funktion muutoskohdan etsiminen.

Oletetaan, että meillä on funktio $f$, jolle pätee $f(k)=0$, kun $k < m$, ja $f(k)=1$, kun $k \ge m$. Binäärihaun avulla löydämme tehokkaasti muutoskohdan $m$ näin:

int k = -1;
for (int b = N; b >= 1; b /= 2) {
    while (f(k+b) == 0) k += b;
}
int m = k+1;

Tässä $N$ on sopiva yläraja, jossa varmasti $f(N)=1$, ja haku etsii viimeisen kohdan $k$, jolle pätee $f(k)=0$. Niinpä haun päätteeksi $m=k+1$. Haku vie aikaa $O(\log N)$.

Esimerkki: Tehdas

Tarkastellaan tehtävää (tämän viikon tehtävä 1), jossa tehtaassa on $n$ konetta, jotka on numeroitu $1,2,\dots,n$. Koneella $i$ vie $k_i$ minuuttia aikaa valmistaa yksi tuote. Mikä on pienin aika, jossa voimme valmistaa $t$ tuotetta?

Hyödyllinen havainto on, että jos aikaa on $a$ minuuttia, voimme valmistaa koneella $i$ yhteensä $\lfloor a/k_i \rfloor$ tuotetta. Vastaavasti käyttämällä kaikkia koneita voimme valmistaa $a$ minuutissa $\sum_{i=1}^n \lfloor a/k_i \rfloor$ tuotetta.

Voimme ratkaista tehtävän binäärihaun avulla muotoilemalla funktion $f$ niin, että $f(a)=0$, jos $\sum_{i=1}^n \lfloor a/k_i \rfloor < t$, ja muuten $f(a)=1$. Nyt funktion $f$ muutoskohta $m$ kertoo, mikä on pienin määrä aikaa, jossa voimme valmistaa $t$ tuotetta.

Jotta voimme käyttää binäärihakua, meidän tulee valita jotenkin parametri $N$. Mahdollinen valinta on $N=k_1 t$. Tämä tarkoittaa, että valmistamme kaikki tuotteet koneen $1$ avulla. Tämä ei selkeästi ole yleensä hyvä tapa, koska muita koneita ei käytetä lainkaan, mutta saamme tästä ylärajan vastaukselle.

Tuloksena oleva algoritmi vie aikaa $O(n \log N)$, koska binäärihaussa on $O(\log N)$ askelta ja jokaisen suorittaminen vie aikaa $O(n)$.